旋转卡壳.cpp

// ps 写了两个旋转卡壳两个凸包 怎么拍都拍不瓦 就是过不了POJ
// update : 已经可以过了！ 把 %lf 改成 %d 就好了。。。 晕死
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define eps (1e-15)
#define maxn 50100
using namespace std;
struct point {
	double x,y;
	point (double x = 0,double y = 0) : x(x), y(y) { }
} dot[maxn],hull[maxn];

point operator - (point a,point b) { return point(a.x - b.x,a.y - b.y); } 
point operator + (point a,point b) { return point(a.x + b.x,a.y + b.y); }
double operator / (point a,point b) { return (a.x * b.y - a.y * b.x); }
double operator * (point a,point b) { return (a.x * b.x + a.y * b.y); }
int i,j,k,l,m,n,top,s,t,hq = -1;
point st[maxn],now;
double ans;

int sig(double a) {
	return (a < -eps ? -1 : (a > eps));
}

bool cmp(const point &a,const point &b) { return sig(a.x - b.x) < 0 || (sig(a.x - b.x) == 0 && sig(a.y - b.y) < 0); }

double length(point a) {
	return (a * a);
}

bool dot_R(point v1,point v2) { // v1 zai v2 de youbian
	return (v1 / v2 > 0 || (v1 / v2 == 0 && sig(length(v1) - length(v2)) <= 0));
}

void get_hull() { // YY版本
	sort(dot + 1,dot + n + 1,cmp);
	st[top = 1] = dot[1];
	int i;
	for (i = 2; i <= n; i++) {
		while (top > 1 && dot_R(dot[i] - st[top],dot[i] - st[top - 1])) top--;
		st[++top] = dot[i];
	}
	for (i = 1; i <= top; i++) hull[++hq] = st[i];
	s = 0; t = hq;
	st[top = 1] = dot[n];
	for (i = n - 1; i; i--) {
		while (top > 1 && dot_R(dot[i] - st[top],dot[i] - st[top - 1])) top--;
		st[++top] = dot[i];
	}
	for (i = 2; i < top; i++) hull[++hq] = st[i];
}

void get_hull_() { // 白书版本
	sort(dot + 1,dot + n + 1,cmp);
	m = 0;
	for (int i = 1; i <= n; i++) {
		while (m > 1 && (hull[m - 1] - hull[m - 2]) / (dot[i] - hull[m - 2]) <= 0) m--;
		hull[m++] = dot[i];
	}
	int k = m;
	for (int i = n - 1; i; i--) {
		while (m > k && (hull[m - 1] - hull[m - 2]) / (dot[i] - hull[m - 2]) <= 0) m--;
		hull[m++] = dot[i];
	}
	if (m > 2) m--;
	hq = m;
}

double get_ang(point a,point b) {
	return acos(a * b / sqrt(length(a)) / sqrt(length(b)));
}

double rotate_() { // yy 版本
	bool mark = true; point v1,v2; double ang1,ang2;
	now = point(0,1); int a = s, b = t; hq++;
	while (mark || s != a || t != b) {
		mark = 0;
		v1 = hull[(t + 1) % hq] - hull[t]; v2 = hull[s] - hull[(s + 1) % hq];
		ang1 = get_ang(v1,now); ang2 = get_ang(v2,now);
		if (ang1 < ang2) { now = v1; ++t %= hq; }
		else { now = v2; ++s %= hq; }
		ans = max(ans,length(hull[s] - hull[t]));
	}
}

double rotate__() { // 网上的版本
	if (hq == 2) (ans = length(hull[0] - hull[1]));
	hull[hq] = hull[0];  t = 1;
	for (s = 0;s < hq; s++) {
		while (fabs((hull[s] - hull[s + 1]) / (hull[t] - hull[s])) < fabs((hull[s] - hull[s + 1]) / (hull[t + 1] - hull[s]))) {
			(++t) %= hq;
		}
		ans = max(ans,max(length(hull[s] - hull[t]),length(hull[s + 1] - hull[t + 1])));
	}
}

point rotate(point a,double b) {
	return point(a.x * cos(b) - a.y * sin(b),a.x * sin(b) + a.y * cos(b));
}

int main() {
	freopen("2187.in","r",stdin);
	freopen("2187.out","w",stdout);
	while (scanf("%d",&n) != EOF) {
		ans = 0; hq = -1;
		for (i = 1; i <= n; i++) {
			scanf("%lf %lf",&dot[i].x,&dot[i].y);
		}
		get_hull_();
		rotate__();
		printf("%.0lf\n",ans);
	}
	return 0;
}