旋转卡壳的地方输出不正确

#1 本地输出0.39 793.50 正确 Linux输出0.39 778.02 洛谷输出0.39 739.12

代码如下

#include<bits/stdc++.h>
#define distance(a,b) sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y))
#define distance2(a,b) (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)
using namespace std;
const int N = 100005;
const double INF = 19198101145.00;
class Point {
	public:
		double x;
		double y;

		Point():x(0),y(0){}
		Point(double x,double y):x(x),y(y) {}
		Point(const Point& A):x(A.x),y(A.y) {}
		~Point() {}
	private:
} a[N],zero;

class Vector {
	public:
		Point A;
		Point B;

		Vector(const Point& A,const Point& B):A(A),B(B) {}
		~Vector() {}
	private:
};

double Cross(const Vector& A,const Vector& B) {
	return (A.B.x - A.A.x) * (B.B.y - B.A.y) - (B.B.x - B.A.x) * (A.B.y - A.A.y);
}
double Dot(const Vector& A,const Vector& B) {
	return (A.B.x - A.A.x) * (B.B.x - B.A.x) + (A.B.y - A.A.y) * (B.B.x - B.A.y);
}
double Len(const Vector& A) {
	return sqrt(Dot(A,A));
}
double Len2(const Vector& A) {
	return Dot(A,A);
}

class Line {
	public:
		Point A;
		Point B;

		Line(){}
		Line(const Point& A,const Point& B):A(A),B(B) {}
		double distanceWithPoint(const Point& point) {
			return fabs(Cross({A,point}, {A,B})) / Len({A,B});
		}
		double distanceWithPoint_f(const Point& point) {
			return fabs(Cross({A,point}, {A,B}));
		}
		~Line() {}
	private:
};

class Hull {
	public:
		Hull():Top(0) {}
		Point& operator[](int index) {
			return points[index + 1];
		}
		void push(const Point& point) {
			points[++ Top] = point;
		}
		void pop() {
			Top --;
		}
		Point& top() {
			return points[Top];
		}
		Point& subtop() {
			if(Top == 0) return zero;
			return points[Top - 1];
		}
		int size() {
			return Top;
		}
	private:
		Point points[N];
		int Top;
}h;

bool cmp(const Point& A,const Point& B) {
	double cross = Cross({a[1],A}, {a[1],B});
	if(cross > 0) return true;
	if(cross == 0 && distance(zero,A) < distance(zero,B)) return true;
	return false;
}

double RotatingCalipers(Hull& hull) {
	if(hull.size() == 3) return distance2(hull[0],hull[1]);
	int cur = 0;
	double ans = 0;
	const int size = hull.size();
	for(int i = 0; i < size - 1; ++ i) {
		Line line(hull[i],hull[i + 1]);
		while(line.distanceWithPoint_f(hull[cur]) <= line.distanceWithPoint_f(hull[(cur + 1) % size])){
			cur = (cur + 1) % size;
		}
		ans = max(ans,max(distance2(hull[i],hull[cur]),distance2(hull[i + 1],hull[cur])));
	}
	return sqrt(ans);
}

bool cmpx(const Point& A,const Point& B) {
	return A.x < B.x;
}

bool cmpy(const	int A,const int B) {
	return a[A].y < a[B].y;
}

double solve(int l,int r) {
	if(l == r) return INF;
	if(l + 1 == r) return distance(a[l],a[r]);
	int mid = (l + r) >> 1;
	double ans = solve(l,mid);
	ans = min(ans,solve(mid + 1,r));
	vector<int> v;
	v.clear();
	for(int i = l;i <= r;++ i){
		if(distance(a[i],a[mid]) <= ans) v.push_back(i);
	}
	sort(v.begin(),v.end(),cmpy);
	const int size = v.size();
	for(int i = 0;i < size;++ i){
		for(int j = i + 1;j < size && a[v[j]].y - a[v[i]].y < ans;++ j){
			ans = min(ans,distance(a[v[i]],a[v[j]]));
		}
	}
	return ans;
}

int main() {
	zero = {-2000,-2000};
	int n;
	scanf("%d",&n);
	for(int i = 1; i <= n; ++ i) {
		scanf("%lf %lf",&a[i].x,&a[i].y);
		if(a[i].y <= a[1].y) {
			if(a[i].y == a[1].y && a[i].x > a[1].x) continue;
			swap(a[i],a[1]);
		}
	}
	sort(a + 2,a + n + 1,cmp);
	h.push(a[1]);
	for(int i = 2; i <= n; ++ i) {
		while(h.size() > 1 && Cross({h.subtop(),h.top()}, {h.top(),a[i]}) <= 0) h.pop();
		h.push(a[i]);
	}
	h.push(a[1]);
	double ans_max = RotatingCalipers(h);
	
	sort(a + 1,a + n + 1,cmpx);
	double ans_min = solve(1,n);
	
	printf("%0.2f %0.2f",ans_min,ans_max);
	return 0;
}