Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 28462 | Accepted: 9498 |
Description
Input
Output
Sample Input
9 100 200 400 300 400 300 300 400 300 400 400 500 400 500 200 350 200 200 200
Sample Output
1628
Hint
Source
1 #include <iostream>
2 #include <cmath>
3 #include <iomanip>
4 #include <stdio.h>
5 using namespace std;
6 struct Point{
7 double x,y;
8 };
9 double dis(Point p1,Point p2)
10 {
11 return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
12 }
13 double xmulti(Point p1,Point p2,Point p0) //求p1p0和p2p0的叉积,如果大于0,则p1在p2的顺时针方向
14 {
15 return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
16 }
17 double graham(Point p[],int n) //点集和点的个数
18 {
19 int pl[10005],i;
20 //找到纵坐标(y)最小的那个点,作第一个点
21 int t = 1;
22 for(i=1;i<=n;i++)
23 if(p[i].y < p[t].y)
24 t = i;
25 pl[1] = t;
26 //顺时针找到凸包点的顺序,记录在 int pl[]
27 int num = 1; //凸包点的数量
28 do{ //已确定凸包上num个点
29 num++; //该确定第 num+1 个点了
30 t = pl[num-1]+1;
31 if(t>n) t = 1;
32 for(i=1;i<=n;i++){ //核心代码。根据叉积确定凸包下一个点。
33 double x = xmulti(p[i],p[t],p[pl[num-1]]);
34 if(x<0) t = i;
35 }
36 pl[num] = t;
37 } while(pl[num]!=pl[1]);
38 //计算凸包周长
39 double sum = 0;
40 for(i=1;i<num;i++)
41 sum += dis(p[pl[i]],p[pl[i+1]]);
42 return sum;
43 }
44 const double PI = 3.1415927;
45 int main()
46 {
47 int N,i;
48 double L;
49 Point p[1005];
50 cout<<setiosflags(ios::fixed)<<setprecision(0);
51 while(scanf("%d%lf",&N,&L)!=EOF){
52 for(i=1;i<=N;i++)
53 scanf("%lf%lf",&p[i].x,&p[i].y);
54 printf("%d\n",int(graham(p,N)+2*PI*L+0.5));
55 }
56 return 0;
57 }
Freecode : www.cnblogs.com/yym2013
poj 1113:Wall(计算几何,求凸包周长),布布扣,bubuko.com
原文:http://www.cnblogs.com/yym2013/p/3673200.html