程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> nyoj253LK的旅行(旋轉卡殼法)

nyoj253LK的旅行(旋轉卡殼法)

編輯:C++入門知識

nyoj253LK的旅行(旋轉卡殼法)


LK的旅行

時間限制:2000 ms | 內存限制:65535 KB 難度:5
描述
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;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved