289
POJ 2187 凸包+旋轉卡殼
題意：求凸包最長點對，輸出兩點距離的平方。
先求凸包，再旋轉卡殼求直徑
關於旋轉卡殼的具體實現 https://www.cppblog.com/staryjy/archive/2009/11/19/101412.html
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef int PointType;
struct point
{
PointType x,y;
int num;
};
point data[50005],stack[51005],MinA;
int top;
PointType Direction(point pi,point pj,point pk) //判斷向量PiPj在向量PiPk的順逆時針方向 +順-逆0共線
{
return (pj.x-pi.x)*(pk.y-pi.y)-(pk.x-pi.x)*(pj.y-pi.y);
}
PointType Dis(point a,point b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool cmp(point a,point b)
{
PointType k=Direction(MinA,a,b);
if(k>0) return 1;
if(k<0) return 0;
return Dis(MinA,a)>Dis(MinA,b);
}
void Graham_Scan(point *a,int numa)
{
for(int i=0; i<numa; i++)
if(a[i].y<a[0].y||(a[i].y==a[0].y&&a[i].x<a[0].x))
swap(a[i],a[0]);
MinA=a[0],top=0;
sort(a+1,a+numa,cmp);
stack[top++]=a[0],stack[top++]=a[1],stack[top++]=a[2];
for(int i=3; i<numa; i++)
{
while(Direction(stack[top-2],stack[top-1],a[i])<0)
top--;
stack[top++]=a[i];
}
}
PointType rotating_calipers(point *ch,int n)//計算凸包直徑，輸入凸包ch，頂點個數為n，按逆時針排列，輸出直徑的平方
{
int q=1,ans=0;
ch[n]=ch[0];
for(int p=0; p<n; p++)
{
while(Direction(ch[p+1],ch[q+1],ch[p])>Direction(ch[p+1],ch[q],ch[p]))
q=(q+1)%n;
ans=max(ans,max(Dis(ch[p],ch[q]),Dis(ch[p+1],ch[q+1])));
}
return ans;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i=0; i<n; i++)
scanf("%d%d",&data[i].x,&data[i].y);
Graham_Scan(data,n);
printf("%d\n",rotating_calipers(stack,top));
}
return 0;
}
最後更新：2017-04-03 21:30:16