求助Andrew
查看原帖
求助Andrew
151647
sycqwq楼主2022/1/18 21:53

rt

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct node
{
	double x,y;
	int id;
}a[maxn];
int n;
node line(node x1,node x2)
{
	return (node){x1.x-x2.x,x1.y-x2.y,1};
}
int operator*(node x1,node x2)
{
	return x1.x*x2.y-x1.y*x2.x;
}
//stack<node> s;
int cmp(node s1,node s2)
{
	return (s1.x<s2.x)||(s1.x==s2.x&&s1.y<s2.y);
}
double dis(node s1,node s2)
{
	return sqrt((s1.x-s2.x)*(s1.x-s2.x)+(s1.y-s2.y)*(s1.y-s2.y));
}
int tot,bk[maxn];
node ans[maxn];
double andrew()
{
	stack<node> q;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
		a[i].id=i;
	q.push(a[1]);
	bk[1]=1;
	node lst;
	lst.x=lst.y=0;
	for(int i=2;i<=n;i++)
	{
		while(q.size()>=2&&line(q.top(),lst)*line(a[i],lst)<0)
		{
			bk[q.top().id]=0;
			q.pop();
			if(q.size()>=2)
			{
			
				node tp=q.top();
				q.pop();
				lst=q.top();
				q.push(tp);
			}
		}		
		bk[i]=1;
		lst=q.top();
		q.push(a[i]);
	}
	for(int i=n-1;i>=1;i--)
	{
		if(!bk[i])
		{
			
			while(q.size()>=2&&line(q.top(),lst)*line(a[i],lst)<0)
			{
				bk[q.top().id]=0;
				q.pop();
				if(q.size()>=2)
				{
					node tp=q.top();
					q.pop();
					lst=q.top();
					q.push(tp);
				}
			}
			bk[i]=1;
			lst=q.top();
			q.push(a[i]);
		}
	}
	while(!q.empty())
	{
		ans[++tot]=q.top();
//		cout<<q.top().x<<' '<<q.top().y<<endl;
		q.pop();
	}
	double s=dis(ans[1],ans[tot]);
	for(int i=1;i<tot;i++)
	{
		s+=dis(ans[i],ans[i+1]);
//		cout<<s<<endl;
	}
	return s;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i].x>>a[i].y;
	printf("%.2lf",andrew());
	return 0;
}
2022/1/18 21:53
加载中...