題目大意：
給一堆點，求直線距離最遠的兩個點。

思路：
就是求“凸多邊形的直徑”。google一下，很多結果的啦。
首先要求出凸包，然后用一個比較牛逼的算法貌似可以在O(N)時間內求出凸包直徑。
但是那算法太復雜啦，看了半天都看不懂，所以就枚舉凸包每兩個點之間的距離了。
還是能200+ms過，因為凸包求出來以后，N就大大減小了。

#include <stdio.h>
#include <stdlib.h>

struct point {
    short x, y;
};
struct point points[50024], *convex[50024];
int points_cnt, convex_cnt;

__inline void swap(struct point *a, struct point *b)
{
    struct point t = *a;
    *a = *b;
    *b = t;
}

__inline int cmp(struct point *p1, struct point *p2)
{
    int a, b, c, d, r;
    
    a = p1->y - points[0].y;
    b = p1->x - points[0].x;
    c = p2->y - points[0].y;
    d = p2->x - points[0].x;
    r = a*d - b*c;
    if (!r) {
        if (b)
            return b - d;
        return a - c;
    }
    return r;
}

__inline int turn_left(struct point *p1, struct point *p2, struct point *p3)
{
    return    (int)p1->x*p2->y - (int)p1->x*p3->y - (int)p2->x*p1->y + 
            (int)p3->x*p1->y + (int)p2->x*p3->y - (int)p3->x*p2->y
            >= 0;
}

void qs(struct point *arr, int len)
{
    int l, r, p;
    
    if (len < 2)
        return ;

    l = 0;
    p = len - 1;
    r = len - 2;
    while (1) {
        while (l < p && cmp(&arr[l], &arr[p]) < 0)
            l++;
        while (r >= 0 && cmp(&arr[r], &arr[p]) >= 0)
            r--;
        if (l > r)
            break;
        swap(&arr[l], &arr[r]);
    }
    swap(&arr[l], &arr[p]);

    qs(arr, l);
    qs(arr + l + 1, len - l - 1);
}

int main()
{
    int i, j, x, y, left, down, min_idx, max_val, val;

    freopen("e:\\test\\in.txt", "r", stdin);

    scanf("%d", &points_cnt);
    left = down = 0x7fffffff;
    for (i = 0; i < points_cnt; i++) {
        scanf("%d%d", &x, &y);
        points[i].x = x;
        points[i].y = y;
        if (x < left || (x == left) && y < down) {
            left = x;
            down = y;
            min_idx = i;
        }
    }
    swap(&points[0], &points[min_idx]);
    qs(points + 1, points_cnt - 1);

    convex_cnt = 0;
    convex[convex_cnt++] = &points[0];
    convex[convex_cnt++] = &points[1];
    for (i = 2; i < points_cnt; i++) {
        while (convex_cnt >= 2 && 
               !turn_left(convex[convex_cnt - 2], 
                         convex[convex_cnt - 1],
                         &points[i]))
        {
              convex_cnt--;
        }
        convex[convex_cnt++] = &points[i];
    }

    max_val = 0;
    for (i = 0; i < convex_cnt - 1; i++) {
        for (j = i + 1; j < convex_cnt; j++) {
            x = convex[i]->x - convex[j]->x;
            y = convex[i]->y - convex[j]->y;
            val = x*x + y*y;
            if (val > max_val)
                max_val = val;
        }
    }
    printf("%d\n", max_val);

    return 0;
}