POJ2187 (Beauty Contest)[凸包，旋转卡壳，平面最远点对]

发表于 | 更新于 | | 阅读次数：

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

首先，距离最大的点对一定都在凸包上。
若凸包上两个顶点能落在一对平行切线上，则称他们为对踵点。
显然，答案一定取在一组对踵点对。
如何做？
类似双指针
枚举凸包上的边，找出距离此边最远的点，因为凸包上点到边距离为单峰函数，也就是说点到边构成的三角形面积是单峰函数，因此可以利用叉积比较面积。
注意：不能枚举凸包上的点（而不是枚举边），用上述做法找出距离此固定点最远的点。因为不满足最重要的单峰性
引用自HIT_Tom课件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps=1e-8;
const double inf=1e20;
const double pi=acos(-1.0);
const int maxn=200009;
int sgn(int x) {
    if(fabs(x)<eps) return 0;
    if(x<0) return -1;
    else return 1;
}
inline int sqr(int x) { return x*x; }
struct Point {
    int x,y;
    Point() {}
    Point(int _x,int _y) {
        x=_x;
        y=_y;
    }
    int distance(Point p) {
        return sqr(p.x-x)+sqr(p.y-y);
    }
//    double len() {
//        return hypot(x,y);
//    }
    int dis2(Point p) {
        return sqr(p.x-x)+sqr(p.y-y);
    }
    bool operator ==(Point b) const {
        return sgn(x-b.x)==0 && sgn(y-b.y)==0;
    }
    bool operator <(Point b) const {
        return sgn(x-b.x)==0 ? sgn(y-b.y)<0:x<b.x;
    }
    Point operator -(const Point& b) const {
        return Point(x-b.x,y-b.y);
    }
    Point operator +(const Point& b) const {
        return Point(x+b.x,y+b.y);
    }
    int operator ^(const Point& b) const {
        return x*b.y-y*b.x;
    }
    int operator *(const Point& b) const {
        return x*b.x+y*b.y;
    }
};
struct polygon {
    int n;
    Point p[maxn];
    void add(Point q) {
        p[n++]=q;
    }
    void init() {
        n=0;
    }
    inline int nex(int i) {
        return (i+1)%n;
    }
    int getans() {
        int ans=0;
        for(int i=0,j=1;i<n;i++) {
            while(abs((p[nex(i)]-p[i])^(p[nex(j)]-p[i])) > abs((p[nex(i)]-p[i])^(p[j]-p[i])))
                j=nex(j);
            ans=max(ans,p[i].dis2(p[j]));
        }
        return ans;
    }
    struct cmp {
        Point p;
        cmp(const Point& p0) { p=p0; }
        bool operator ()(const Point& aa,const Point& bb) {
            Point a=aa,b=bb;
            int d=sgn((a-p)^(b-p));
            if(d==0) {
                return sgn(a.distance(p)-b.distance(p)) < 0;
            }
            return d > 0;
        }
    };
    void norm() {
        Point mi=p[0];
        for(int i=1;i<n;i++) mi=min(mi,p[i]);
        sort(p,p+n,cmp(mi));
    }
    void Graham(polygon &convex) {
        norm();
        int &top=convex.n;
        top=0;
        if(n==1) {
            top=1;
            convex.p[0]=p[0];
            return ;
        }
        if(n==2) {
            top=2;
            convex.p[0]=p[0];
            convex.p[1]=p[1];
            if(convex.p[0]==convex.p[1]) top--;
            return ;
        }
        convex.p[0]=p[0];
        convex.p[1]=p[1];
        top=2;
        for(int i=2;i<n;i++) {
            while(top>1 && sgn((convex.p[top-1]-convex.p[top-2])
                ^(p[i]-convex.p[top-2]))<=0)
                    top--;
            convex.p[top++]=p[i];
        }
        if(convex.n==2 && (convex.p[0]==convex.p[1])) convex.n--;
    }
}poly,con;
int main() {
    int n;
    scanf("%d",&n);
    int x,y;
    poly.init();
    for(int i=0;i<n;i++) {
        scanf("%d%d",&x,&y);
        poly.add(Point(x,y));
    }
    con.init();
    poly.Graham(con);
    printf("%d",con.getans());
}