nyoj253LK的旅行（旋轉卡殼法）

nyoj253LK的旅行（旋轉卡殼法）

LK的旅行

描述

LK最近要去某幾個地方旅行，她從地圖上計劃了幾個點，並且用筆點了出來，准備在五一假期去這幾個城市旅行。現在希望你找出她點的所有的點中距離最遠的兩個點的距離是多少。各個景點可以認為是在一個平面上。

輸入

第一行有一個整數0 輸出

每組數據輸出距離最遠的點對的距離的平方.

樣例輸入

1
4
0 0
1 1
0 1
1 0

樣例輸出

2

做這個題之前最好先做下78圈水池這題，這兩個題差不多，區別在於一個是求哪些點在凸包內，這個是求凸包的兩個最遠的點的距離的平方。

#include
#include
#include
#define NN 100005
#define max(a,b) ((a)>(b)?(a):(b))
const int INF=1<<30;
typedef struct Point{
	int x,y;
}P;
P a[NN],q[NN];
int top;
int dis_2(P p1,P p2)
{
	return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}
int xx(P p,P p1,P p2)
{
	return (p1.x-p.x)*(p2.y-p.y)-(p1.y-p.y)*(p2.x-p.x);
}
int comp(const void *x,const void *y)
{
	P i=*(P *)x;
	P j=*(P *)y;
	if(i.x!=j.x)
		return i.x-j.x;
	else
		return i.y-j.y;
}
int main()
{
	int N,i,n;
	scanf("%d",&N);
	while(N--)
	{
		scanf("%d",&n);
		for(i=0;i=1 && xx(q[top-1],q[top],a[i])>=0) top--;
			q[++top]=a[i];
		}
		int t=top;
		for(i=n-1;i>=0;i--)//上凸包
		{
			if(a[i].x==q[top].x && a[i].y==q[top].y) continue;
			while(top>t && xx(q[top-1],q[top],a[i])>=0) top--;
			q[++top]=a[i];
		}	
		double ans=0.0;
		t=1;
		for(i=0;i xx(q[i+1],q[t+1],q[i])) t=(t+1)%top;
			ans=max(ans,max(dis_2(q[i],q[t]),dis_2(q[i+1],q[t+1])));
		}
		printf("%.0lf\n",ans);		
	}
	return 0;
}