学步园

题目链接：http://poj.org/problem?id=2187

 第一个最远点对。求的是最远点对的平方。

求最远点对，我们应该知道一条性质，最远点对，一定是这一系列点的凸包上的两个点。这道题，直接枚举凸包上的点就可以。当然，旋转卡壳也是可以的。

直接求凸包+枚举点。OK。

Code：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;

const int N = 5 * 1e4 + 5;
const double eps = 1e-8;

struct POINT{
    double x, y;
}p[N], st[N];
int n, top;

double cross(POINT o, POINT a, POINT b){
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

double Distance(POINT a, POINT b){
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

bool cmp(POINT a, POINT b){
    if(a.y < b.y) return true;
    else if(a.y == b.y && a.x < b.x) return true;
    return false;
}

bool cmp1(POINT a, POINT b){
    if(cross(p[0], a, b) > eps) return true;
    else if(fabs(cross(p[0], a, b)) < eps && fabs(Distance(p[0], a) - Distance(p[0], b)) > eps)return true;
    return false;
}


bool Judge(POINT a, POINT b, POINT c){
    if(cross(a, b, c) > eps) return true;
    else if(fabs(cross(a, b, c)) < eps && Distance(b, a) < Distance(b, c)) return true;
    else return false;
}

void Graham_scan(){
    sort(p, p + n, cmp);
    sort(p + 1, p + n, cmp1);
    top = 0;
    st[top ++] = p[0]; st[top ++] = p[1];
    for(int i = 2; i < n; i ++){
        while(top >= 2 && Judge(st[top - 1], st[top - 2], p[i])) top --;
        st[top ++] = p[i];
    }
}

double ALL(){
    double ans = 0;
    for(int i = 0; i < top - 1; i ++){
        for(int j = i + 1; j < top; j ++)
        if(Distance(st[i], st[j]) - ans > eps)
        ans = Distance(st[i], st[j]);
    }
    return ans;
}

int main(){
//    freopen("1.txt", "r", stdin);
    while(~scanf("%d", &n)){
        for(int i = 0; i < n; i ++){
            scanf("%lf %lf", &p[i].x, &p[i].y);
        }
        Graham_scan();
        printf("%.0lf\n", ALL());
    }
    return 0;
}

旋转卡壳还是需要学习的，枚举点在某些问题上的时间复杂度太高。