poj 1113 & poj 2187

凸包问题

题意就是给你一些点，然后让你求凸包并求出这个凸包的周长，由于题目中有要求，所以求出周长后还要再加上一个以输入 L 为半径的园的周长，才是所求的答案

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <stdlib.h>
 6 #include <math.h>
 7 #define N 1010
 8 #define pi 3.1415926
 9 
10 using namespace std;
11 
12 struct node
13 {
14     double x;
15     double y;
16 }point[N],stack[N];
17 int n,top,l;
18 double dis(node a,node b)
19 {
20     return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
21 }
22 double mul(node &a,node &b,node &c)
23 {
24     return (c.x - a.x) * (b.y - a.y) - (b.x - a.x) * (c.y - a.y);
25 }
26 /* 极角排序 */
27 int cmp(const void *a,const void *b)
28 {
29     node *c = (node *) a;
30     node *d = (node *) b;
31     int m = mul(point[0],*c,*d);
32     if(m == 0) return dis(*c,point[0]) - dis(*d,point[0]);
33     else return -m;
34 }
35 /*  */
36 void gramham()
37 {
38     top = 1;
39     qsort(point + 1,n - 1,sizeof(node),cmp);
40     stack[0] = point[0];
41     stack[1] = point[1];
42     int i;
43     for(i = 2; i < n; i++)
44     {
45         while(top >= 1 && mul(stack[top - 1],stack[top],point[i]) <= 0)  // 根据叉积判断是左转还是右转
46         top --;
47         stack[++top] = point[i];
48     }
49 }
50 int main()
51 {
52     int i;
53     int kemp;
54     double maxx;
55     //freopen("data.txt","r",stdin);
56     while(cin>>n>>l)
57     {
58         memset(point,0,sizeof(point));
59         memset(stack,0,sizeof(stack));
60         kemp = 0;
61         for(i = 0; i < n; i++)
62         {
63             scanf("%lf%lf",&point[i].x,&point[i].y);
64             if(point[i].y < point[kemp].y || (point[i].y == point[kemp].y && point[i].x < point[kemp].x))  // 查找最靠下，靠左的点
65             kemp = i;
66         }
67         swap(point[0],point[kemp]);
68         gramham();
69         stack[top + 1] = stack[0];
70         maxx = 0;
71         for(i = 0; i < top + 1; i++)
72         {
73             maxx += (dis(stack[i],stack[i + 1]) * 1.0);
74         }
75         maxx += pi * 2 * l;
76         printf("%.0lf\n",maxx);
77     }
78     return 0;
79 }

poj 2187

题意：利用凸包求最远距离，与上题方法一样不多解释了

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <stdlib.h>
 6 #define N 50010
 7 
 8 using namespace std;
 9 
10 struct node
11 {
12     int x;
13     int y;
14 }point[N],stack[N];
15 int n,top;
16 int dis(node &a,node &b)
17 {
18     return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
19 }
20 int mul(node &a,node &b,node &c)
21 {
22     return (c.x - a.x) * (b.y - a.y) - (b.x - a.x) * (c.y - a.y);
23 }
24 int cmp(const void *a,const void *b)
25 {
26     node *c = (node *) a;
27     node *d = (node *) b;
28     int m = mul(point[0],*c,*d);
29     if(m == 0) return dis(*c,point[0]) - dis(*d,point[0]);
30     else return -m;
31 }
32 void gramham()
33 {
34     top = 1;
35     qsort(point + 1,n - 1,sizeof(node),cmp);
36     stack[0] = point[0];
37     stack[1] = point[1];
38     int i;
39     for(i = 2; i < n; i++)
40     {
41         while(top >= 1 && mul(stack[top - 1],stack[top],point[i]) <= 0)
42         top --;
43         stack[++ top] = point[i];
44     }
45 }
46 int main()
47 {
48     int i,j;
49     int kemp;
50     int maxx;
51     //freopen("data.txt","r",stdin);
52     while(cin>>n)
53     {
54         memset(point,0,sizeof(point));
55         memset(stack,0,sizeof(stack));
56         kemp = 0;
57         for(i = 0; i < n; i++)
58         {
59             scanf("%d%d",&point[i].x,&point[i].y);
60             if(point[i].y < point[kemp].y || (point[i].y == point[kemp].y && point[i].x < point[kemp].x))
61             kemp = i;
62         }
63         swap(point[0],point[kemp]);
64         gramham();
65         maxx = 0;
66         for(i = 0; i <= top; i++)
67         {
68             for(j = i + 1; j <= top; j++)
69             maxx = max(maxx,dis(stack[i],stack[j]));
70         }
71         cout<<maxx<<endl;
72     }
73     return 0;
74 }