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;
}

补充：软件开发 , C++ ,