最远点对

the longest distanceSubmit: 246   Accepted:64Time Limit: 1000MS  Memory Limit: 65535KDescription
给你平面上n 个点，请你找出距离最远的两个点。

Input
多组数据测试
第一行一个正整数n,表示平面有n个点。后面n行，每行两个整数x,y,表示第i个点的坐标。
数据范围
2 <= n <= 50000
-10000 <= x,y <= 10000


Output
每组数据一行，最远的距离，小数点后保留三位(四舍五入)。


Sample Input

3
0 0
1 1
3 4


Sample Output

5.000


凸包，Graham-scan
极角排序，依次寻找向左转的点，构成凸包
最远点对是凸包直径的两个点

注意叉积在判断线段转向时的使用

#include <stdio.h>
#include <math.h>

#define MAX_INT 0x7fffffff
#define EPS 1e-6

typedef struct _point
{
    double x;
    double y;
}ST_POINT;

ST_POINT points[50010], stack[50010];

int angle_comp(const void *a, const void *b)
{
    ST_POINT *p1 = (ST_POINT *)a;
    ST_POINT *p2 = (ST_POINT *)b;
    double x0, y0, x1, y1, x2, y2, t;
    x0 = (double)(points[0].x);
    y0 = (double)(points[0].y);
    x1 = (double)(p1->x);
    y1 = (double)(p1->y);
    x2 = (double)(p2->x);
    y2 = (double)(p2->y);

    t = (x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0);
    if (t > EPS)
        return -1;
    else if (fabs(t) < EPS)
        return 0;
    else
        return 1;
}

void angle_sort(ST_POINT *p, int size)
{
    int i, k;
    ST_POINT temp;
    
    k = 0;
    for (i=0 ; i<size ; i++)
    {
        if (p[i].y < p[k].y || ((p[i].y - p[k].y) < EPS && p[i].x < p[k].x))
            k = i;
    }
    /* p[0] is minimal */
    temp = p[0];
    p[0] = p[k];
    p[k] = temp;
    qsort(p + 1, size - 1, sizeof(ST_POINT), angle_comp);
}

double mutiply(ST_POINT *sp, ST_POINT *ep, ST_POINT *op)
{
    return (sp->x - op->x) * (ep->y - op->y) - (ep->x - op->x) * (sp->y - op->y);
}

void Graham_scan(ST_POINT *p, int size, ST_POINT *stack, int *len)
{
    int i, top;

    angle_sort(p, size);
    if (size < 3)
    {
        *len = size;
        for (i=0 ; i<size ; i++)
            stack[i] = p[i];
        return ;
    }

    stack[0] = p[0];
    stack[1] = p[1];
    stack[2] = p[2];
    top = 2;
    for (i=3 ; i<size ; i++)
    {
        while (mutiply(&p[i], &stack[top], &stack[top - 1]) > 0.0)
            top--;
        stack[++top] = p[i];
    }
    *len = top + 1;
}

double distance(ST_POINT *a, ST_POINT *b)
{
    return sqrt((a->x - b->x) * (a->x - b->x) + (a->y - b->y) * (a->y - b->y));
}

double find_diameter(ST_POINT *stack, int len)
{
    int i, j;
    double max_dis, dis;

    for (i=0 ; i<len-1 ; i++)
    {
        for (j=i+1 ; j<len ; j++)
        {
            dis = distance(&stack[i], &stack[j]);
            if (dis > max_dis)
                max_dis = dis;
        }
    }
    
    return max_dis;
}

int main(int argc, char *argv[])
{
    int n, i, len;
    double diameter;
    
    while (EOF != scanf("%d", &n))
    {
        for (i=0 ; i<n ; i++)
            scanf("%lf %lf", &points[i].x, &points[i].y);

        Graham_scan(points, n, stack, &len);
        diameter = find_diameter(stack, len);
        printf("%.3lf\n", diameter);
    }
}