1 #include<iostream>
2 #include<cmath>
3 #include<vector>
4 #include<algorithm>
5 #include<cstdio>
6 using namespace std;
7 const int maxn = 60000;
8
9 struct Point { // 二維點或矢量
10 int x, y;
11 Point() {}
12 Point(int x0, int y0): x(x0), y(y0) {}
13 };
14
15
16 struct Polygon{
17 Point p[maxn];
18 int n;
19 };
20
21 //二維矢量運算
22 bool operator==(Point p1, Point p2)
23 {
24 return ( p1.x - p2.x==0 && p1.y - p2.y==0);
25 }
26 bool operator!=(Point p1, Point p2)
27 {
28 return ( p1.x - p2.x != 0 || p1.y - p2.y != 0);
29 }
30 bool operator<(Point p1, Point p2)
31 {
32 return p1.x < p2.x || p1.x - p2.x==0 && p1.y < p2.y;
33 }
34 Point operator+(Point p1, Point p2)
35 {
36 return Point(p1.x + p2.x, p1.y + p2.y);
37 }
38 Point operator-(Point p1, Point p2)
39 {
40 return Point(p1.x - p2.x, p1.y - p2.y);
41 }
42 int operator*(Point p1, Point p2) // 計算叉乘 p1 × p2
43 {
44 return (p1.x * p2.y - p2.x * p1.y);
45 }
46 int operator&(Point p1, Point p2) { // 計算點積 p1·p2
47 return (p1.x * p2.x + p1.y * p2.y);
48 }
49
50
51 //Graham 凸包
52
53 Polygon Convex_Hull( Point FP[], int fn)
54 {
55 int i, k;
56 Polygon res;
57 sort(FP, FP+fn );
58 res.n = 0;
59 for(i = 0; i < fn; ++i )
60 {
61 while(res.n>=2 && ( res.p[res.n-1] - res.p[res.n-2] ) *( FP[i] - res.p[res.n-2] ) <= 0) res.n--;
62 res.p[res.n++] = FP[i];
63 }
64 k = res.n;
65 for(i = fn-2; i>=0; i--)
66 {
67 while(res.n > k && ( res.p[res.n-1] - res.p[res.n-2]) * ( FP[i] - res.p[res.n-2] ) <= 0 ) res.n--;
68 res.p[res.n++] = FP[i];
69 }
70 res.n--;
71 return res;
72 }
73
74 Polygon ans;
75 Point FP[maxn];
76 int FN;
77
78 int main(){
79 int i, j;
80 int dis, best = -1;
81 scanf("%d",&FN);
82 for(i = 0; i < FN; i++)
83 scanf("%d%d",&FP[i].x , &FP[i].y);
84 ans = Convex_Hull( FP, FN);
85 for(i = 0; i < ans.n; i++)
86 for(j = 0; j < ans.n; j++)
87 {
88 dis = (ans.p[i].x - ans.p[j].x)*(ans.p[i].x - ans.p[j].x)+(ans.p[i].y - ans.p[j].y)*(ans.p[i].y - ans.p[j].y);
89 if(dis > best)best = dis;
90 }
91 printf("%d\n",best);
92 }
能使用整點函數的盡量使用整點函數，避免精度問題
posted on 2009-09-01 08:48
wangzhihao 閱讀(157)
評論(0) 編輯 收藏 引用 所屬分類:
geometry