[POJ2187 Beauty Contest]【凸包+旋转卡壳】

【题目大意】
求平面距离最远的点对。
【算法分析】
凸包。
旋转卡壳求出对踵点。
就是弄两个向量，一个贴着凸包上某条边，另一个于该向量平行并与凸包相交，并使得这两个向量把整个图都夹在中间。
【其它】
以前n^2水过。。。于是重写。
另外我这种转法不是按最小角度转的，于是凸包上要注意去掉共线3点的情况。
去这种情况有点小技巧。。。。就是先判他们凸包连续的3点是否共线。然后在构造两个向量。
P:L[i-1]->L[i]
Q:L[i]->L[i+1]
然后用点积判他们方向是否相同，如果相同那就删，否则是不能删的。。。
（YY一下只有两个点的凸包）
【CODE】
#include #include #include #include #define dis(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;
struct Point{int x,y;}a[N],L[N],Std;
int n,tot,v[N];

int Del_cmp(const void *A,const void *B){
Point P=*((Point*)A),Q=*((Point*)B);
if (P.x!=Q.x) return P.x-Q.x;
return P.y-Q.y;
}

void Delsame(){
qsort(a+1,n,sizeof(Point),Del_cmp);
int i,t=1;
for (i=2;i<=n;i++)
if (a[i].x!=a[i-1].x || a[i].y!=a[i-1].y)
a[++t]=a[i];
n=t;
}

int CJ(Point Z,Point A,Point B){
return (A.x-Z.x)*(B.y-Z.y)-(A.y-Z.y)*(B.x-Z.x);
}

int cmp(const void *A,const void *B){
int res=CJ(Std,*((Point*)A),*((Point*)B));
if (res) return res;
return (((Point*)A)->x+((Point*)A)->y-((Point*)B)->x-((Point*)B)->y);
}

void TB(){
Point P,Q,tmp,M;
int i,j;
M.x=M.y=0x7FFFFFFF;
for (i=1;i<=n;i++)
if (a[i].x M=a[i];
j=i;
}
tmp=a[1]; a[1]=a[j]; a[j]=tmp;
Std=a[1];
qsort(a+2,n-1,sizeof(Point),cmp);
L[1]=a[1];
a[n+1]=a[1];
for (tot=1,i=2;i<=n+1;i++){
while (tot>1 && CJ(L[tot-1],L[tot],a[i])>0) tot–;
L[++tot]=a[i];
}
tot–;
}

void Del_Useless_Point(){
if (tot<3) return;
Point P,Q;
int i,j;
for (i=1;i<=tot;i++) v[i]=0;
L[0]=L[tot]; L[tot+1]=L[1];
for (i=1;i<=tot;i++)
if (CJ(L[i-1],L[i],L[i+1])==0){
P.x=L[i].x-L[i-1].x;
P.y=L[i].y-L[i-1].y;
Q.x=L[i+1].x-L[i].x;
Q.y=L[i+1].y-L[i].y;
if (P.x*Q.x+P.y*Q.y>0) v[i]=1;
}
n=0;
for (i=1;i<=tot;i++)
if (!v[i])
a[++n]=L[i];
}

int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x int i,j,ans=0;
Point P,Q;
bool check;
Std.x=Std.y=0;
a[0]=a[n]; a[n+1]=a[1];
for (i=j=1;i<=n;i++){
for (;;j=j==n?1:j+1){
check=true;
P.x=a[i+1].x-a[i].x;
P.y=a[i+1].y-a[i].y;

Q.x=a[j+1].x-a[j].x;
Q.y=a[j+1].y-a[j].y;
if (CJ(Std,P,Q)<0) check=false; Q.x=a[j-1].x-a[j].x;
Q.y=a[j-1].y-a[j].y;
if (CJ(Std,P,Q)<0) check=false;
if (check) break;
}
ans=max(ans,dis(a[i],a[j-1]));
ans=max(ans,dis(a[i],a[j]));
ans=max(ans,dis(a[i],a[j+1]));
}
printf("%dn",ans);
}

int main(){
int i,j;
while (scanf("%d",&n)!=EOF){
for (i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
Delsame();
TB();
Del_Useless_Point();
switch (n){
case 0:puts("0"); break;
case 1:puts("0"); break;
default:RC(); break;
}
}
return 0;
}