凸包

Anderw

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
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm> 
using namespace std;
const int N = 1e5+10;
const double eps = 1e-8;
int n,top;
double ans;
struct point
{
	double x,y;
	point(){}
	point(double a,double b){x = a, y = b;}
}p[N],sta[N];
point operator + (point a,point b){return point(a.x+b.x,a.y+b.y);}
point operator - (point a,point b){return point(a.x-b.x,a.y-b.y);}
point operator * (point a,double k){return point(a.x*k,a.y*k);}
double Dot(point a,point b){return a.x*b.x+a.y*b.y;}
double Cro(point a,point b){return a.x*b.y-a.y*b.x;}
double dis(point a,point b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int dcmp(double x)
{
	if(fabs(x) < eps) return 0;
	return x > 0 ? 1 : -1;
}
bool comp(point a,point b)
{
	if(dcmp(a.x-b.x) == 0) return a.y < b.y;
	return a.x < b.x;
}
int main()
{
	scanf("%d",&n);
	for(int i = 1; i <= n; i++) scanf("%lf%lf",&p[i].x,&p[i].y);
	sort(p+1,p+n+1,comp);
	sta[++top] = p[1]; sta[++top] = p[2];
	for(int i = 3; i <= n; i++) //下凸壳
	{
		while(top >= 2 && Cro(sta[top]-sta[top-1],p[i]-sta[top-1]) < 0) top--;
		sta[++top] = p[i];
	}
	int last = top;
	sta[++top] = p[n]; sta[++top] = p[n-1];//上凸壳
	for(int i = n-2; i >= 1; i--)
	{
		while(top - last >= 2 && Cro(sta[top]-sta[top-1],p[i]-sta[top-1]) < 0) top--;
		sta[++top] = p[i];
	}
	for(int i = 1; i < top; i++) ans += dis(sta[i],sta[i+1]);//起点和终点都在栈中出现了两次
	printf("%.2lf\n",ans);
	return 0;
}

Graham

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
bool comp(point a,point b)
{
	double m = Cro(a-p[1],b-p[1]);//由叉积来判断极角大小，如果a的极角比b小，那么ap一定在bp的顺时针方向
	if(dcmp(m) > 0) return 1;
	if(dcmp(m) == 0 && dcmp(dis(a,p[1])-dis(b,p[1])) < 0) return 1;
	return 0;
}
int main()
{
	scanf("%d",&n);
	for(int i = 1; i <= n; i++)
	{
		scanf("%lf%lf",&p[i].x,&p[i].y);
		if(dcmp(p[i].y-p[1].y) < 0) swap(p[1],p[i]);
		else if(dcmp(p[i].y-p[1].y) == 0 && dcmp(p[i].x-p[1].x) < 0) swap(p[1],p[i]);
	}
	sort(p+2,p+n+1,comp);
	sta[++top] = p[1]; sta[++top] = p[2];
	for(int i = 3; i <= n; i++)
	{
		while(top >= 2 && Cro(sta[top]-sta[top-1],p[i]-sta[top-1]) <= 0) top--;
		sta[++top] = p[i];
	}
	for(int i = 1; i < top; i++) ans += dis(sta[i],sta[i+1]);
	ans += dis(sta[top],sta[1]);
	printf("%.2lf\n",ans);
	return 0;
}

凸包直径

1
2
3
4
5
6
7
8
9
10
11
double Get_zhijing()
{
	double res = 0;
	sta[top + 1] = p[1];//把 sta[top]sta[1] 这条边也要加进去 
	for(int i = 1, j = 2; i <= top; i++)
	{
		while(Cro(sta[i]-sta[j],sta[i+1]-sta[j]) < Cro(sta[i]-sta[j+1],sta[i+1]-sta[j+1])) j = j % top + 1;//找距离 sta[i]sta[i+1] 最远的点
		res = max(res,max(dis(sta[i],sta[j]),dis(sta[i+1],sta[j])));
	}
	return res;
}