poj2187 凸包

給出n個點的坐標，求出點之間最長距離的平方。

解：構建凸包，最長距離的點必在凸包上，暴力枚舉凸包上的點，可以過，不超時。

[csharp] 
#include<stdio.h> 
#include<stdlib.h> 
#include<math.h> 
struct aa 
{ 
    int x,y; 
    double angle; 
}point[51000],stack[51000]; 
 
double count(int x1,int y1,int x2,int y2) 
{ 
    return atan2((double)(y1-y2),(double)(x1-x2)); 
} 
 
void angle(int n,int m) 
{ 
    int i; 
    point[m].angle=-1; 
    for(i=1;i<=n;i++) 
        if(i!=m) 
            point[i].angle=count(point[i].x,point[i].y,point[m].x,point[m].y); 
} 
 
int cmp(const void *a,const void *b) 
{ 
    struct aa *c=(struct aa *)a; 
    struct aa *d=(struct aa *)b; 
    if(c->angle!=d->angle) 
        return (c->angle>d->angle)?1:-1; 
    else 
        if(c->x!=d->x) 
            return c->x-d->x; 
    return c->y-d->y; 
} 
 
int dist(int x1,int y1,int x2,int y2) 
{ 
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2); 
} 
 
int cross(int x1,int y1,int x2,int y2) 
{ 
    return ((x1*y2)-(x2*y1)>0)?1:0; 
} 
 
int Gansan(int n,int top) 
{ 
    int i,j; 
    for(i=4;i<=n;i++) 
    { 
        while(top>=2) 
        { 
            if(cross(stack[top].x-stack[top-1].x,stack[top].y-stack[top-1].y,point[i].x-stack[top].x,point[i].y-stack[top].y)) 
            { 
                stack[++top]=point[i]; 
                break; 
            } 
            else 
                top--; 
        } 
        if(top==1) 
            stack[++top]=point[i]; 
    } 
    return top; 
} 
 
int main() 
{ 
    int i,j,n,m,top,num; 
    scanf("%d",&n); 
    for(i=1,m=1;i<=n;i++) 
    { 
        scanf("%d%d",&point[i].x,&point[i].y); 
        if(point[i].y<point[m].y||(point[i].y==point[m].y&&point[i].x<point[m].x)) 
            m=i; 
    } 
    //計算極角 
    angle(n,m); 
    //極角排序 
    qsort(point+1,n,sizeof(point[0]),cmp); 
 
    if(n==2) 
    { 
        printf("%d\n",dist(point[1].x,point[1].y,point[2].x,point[2].y)); 
        return 0; 
    } 
    stack[1]=point[1]; 
    stack[2]=point[2]; 
    stack[3]=point[3]; 
    top=3; 
    top=Gansan(n,top); 
    for(i=1,m=-1;i<top;i++) 
    { 
        for(j=i+1;j<=top;j++) 
        { 
            num=dist(stack[i].x,stack[i].y,stack[j].x,stack[j].y); 
            if(m<num) 
                m=num; 
        } 
 
    } 
    printf("%d\n",m); 
    return 0; 
}