随笔-21  评论-10  文章-21  trackbacks-0
 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 阅读(126) 评论(0)  编辑 收藏 引用 所属分类: geometry

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理