Beauty Contest(凸包求最远点)

题意：求凸包上最远点距离的平方

思路：开始用旋转卡壳求的最远点，WA，改了好久。。后来又改成枚举凸包上的点。。AC了。。

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <math.h>
 4 using namespace std;
 5 const int N=50005;
 6 int n;
 7 struct Point
 8 {
 9     int x,y;
10     Point(int x = 0,int y = 0):x(x),y(y) {}
11     bool friend operator < (const Point &a,const Point &b)
12     {
13         return a.x < b.x||(a.x==b.x&&a.y < b.y);
14     }
15 
16 } p[N],ch[N];
17 typedef Point Vector;
18 Vector operator-(Point a,Point b)
19 {
20     return Vector(a.x-b.x,a.y-b.y);
21 }
22 int Cross(Vector A,Vector B)
23 {
24     return A.x*B.y-A.y*B.x;
25 }
26 int Distance(Point a,Point b)
27 {
28     return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
29 }
30 int Graham()//判断凸包
31 {
32     sort(p,p+n);
33     int m = 0;
34     for (int i = 0; i < n; i++)
35     {
36         while(m > 1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2]) <= 0)
37             m--;
38         ch[m++] = p[i];
39     }
40     int k = m;
41     for (int i = n-2; i >= 0; i--)
42     {
43         while(m > k && Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2]) <= 0)
44             m--;
45         ch[m++] = p[i];
46     }
47     if (n > 1)
48         m--;
49     return m;
50 }
51 int main()
52 {
53     scanf("%d",&n);
54     for (int i = 0; i < n; i++)
55         scanf("%d %d",&p[i].x,&p[i].y);
56     int cnt = Graham();
57     int ans = 0;
58     for (int i = 0; i < cnt ; i++)
59     {
60         for (int j = 0; j < i; j++)
61         {
62             int dis = Distance(ch[i],ch[j]);
63             ans = max(ans,dis);
64         }
65     }
66     printf("%d
",ans);
67     return 0;
68 }

View Code

旋转卡壳的那段代码，不知道哪错了，先保留着吧。。后期再改。。

 1 int dia_rotating_calipers(int cnt)//旋转卡壳
 2 {
 3     int dia = 0;
 4     int  q = 1;
 5     for (int i = 0; i < cnt; i++)
 6     {
 7         while(Cross(ch[i+1]-ch[i],ch[q+1]-ch[i]) > Cross(ch[i+1]-ch[i],ch[q]-ch[i]))
 8             q = (q+1)%n;
 9         dia = max(dia,max(Distance(ch[i],ch[q]),Distance(ch[i+1],ch[q+1])));
10     }
11     return dia;
12 }

View Code