【凸包】凸包周长

计算几何

传送站：CodeVS1298

凸包模板题吧。

Graham扫描法的思路（转自：http://blog.csdn.net/bone_ace/article/details/46239187)：

P1

写的时候注意同一直线上的顺序！！！！！！

代码或许有些不完善（GG）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define dis(x1,y1,x2,y2) (sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)))
int n,xb,s[100030];
double ans;
struct zb{int x,y;}a[100030];
bool cmp_y(zb x,zb y){return (x.y<y.y) || (x.y==y.y && x.x<y.x);}
bool wj(zb x,zb y){return (x.x*y.y-x.y*y.x>0) || (x.x*y.y-x.y*y.x==0 && dis(x.x,x.y,0,0)<dis(y.x,y.y,0,0));}
bool pd(int p1,int p2,int p3){ //--------------------------叉乘
	zb x=(zb){a[p2].x-a[p1].x,a[p2].y-a[p1].y};
	zb y=(zb){a[p3].x-a[p2].x,a[p3].y-a[p2].y};
	return wj(x,y);
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++){scanf("%d%d",&a[i].x,&a[i].y);}
	
	sort(a+1,a+n+1,cmp_y);
	for (int i=2;i<=n;i++){a[i].x-=a[1].x; a[i].y-=a[1].y;}
	a[1].x=a[1].y=0;
	
	sort(a+2,a+n+1,wj);
	xb=2; s[1]=1; s[2]=2;
	for (int i=3;i<=n;i++){
		while (!pd(s[xb-1],s[xb],i)) xb--;
		s[++xb]=i;
	}
	
	for (int i=1;i<xb;i++) ans+=dis(a[s[i]].x,a[s[i]].y,a[s[i+1]].x,a[s[i+1]].y);
	ans+=dis(a[s[xb]].x,a[s[xb]].y,a[s[1]].x,a[s[1]].y);
	printf("%.1f\n",ans);
	
	return 0;
}