Andrew 0pts求调
查看原帖
Andrew 0pts求调
1063541
ivan11楼主2024/5/1 20:37
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
struct P
{
	double x,y;
}p[10005],q[10005];
long long n;
double ans=0.0;
double direc(P A,P B);
double check(P a,P b,P n);
bool cmp(P a,P b);
int andrew();
double dist(P a,P b);

int main()
{
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>p[i].x>>p[i].y;
	}
	for(int i=1;i<=andrew();++i)
	{
		ans+=dist(q[i] , q[i-1]);
	}
	printf("%.2lf",ans);
	return 0;
}
double direc(P A,P B)
{
	return B.x * A.y - B.y * A.x;
}
double check(P a,P b,P n)
{
	P A;
	A.x = b.x - a.x;
	A.y = b.y - a.y;
	P B;
	B.x = n.x - a.x;
	B.y = n.y - a.y;
	return direc(A,B);
}
bool cmp(P a,P b)
{
	if(a.x != b.x)
	return a.x < b.x;
	return a.y < b.y;
}
int andrew()
{
	sort(p+1,p+n+1,cmp);
	q[1] = p[1];
	q[2] = p[2];
	int t=1;
	for(int i=3;i<=n;++i)
	{
		while(t && check(q[t - 1] , q[t] , p[i]) >= 0) -- t;
		q[++t] = p[i];
	}
	q[++t] = p[n-1];
	for(int i=n-2;i>=1;--i)
	{
		while(t && check(q[t - 1] , q[t] , p[i]) >= 0) -- t;
		q[++t] = p[i];
	}
	return t;
}
double dist(P a,P b)
{
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
2024/5/1 20:37
加载中...