wa82 求助
查看原帖
wa82 求助
549499
Disjoint_cat楼主2022/8/6 09:47

rt,#1 #2 RE

#include<bits/stdc++.h>
#define ll long long
#define db double
using namespace std;
const int N=100005;
const db eps=1e-7,Pi=3.141592653589793;
int n,mit,st[N]={0,1,2},top=2;
struct node
{
	db x,y,ang;
	bool operator<(const node b)const
	{
		return ang+eps<b.ang;
	}
}cow[N],mi;
db Ang(int i,int j)
{
	db t=180.0/Pi*atan((cow[j].y-cow[i].y)/\
	(cow[j].x-cow[i].x));
	return t>=0.0?t:180.0+t;
}
db dis(int i,int j)
{
	return sqrt((cow[j].x-cow[i].x)*(cow[j].x-cow[i].x)+\
	(cow[j].y-cow[i].y)*(cow[j].y-cow[i].y));
}
db ans;
int main()
{
	freopen("P2742_1.in","r",stdin);
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>cow[i].x>>cow[i].y;
	mi=cow[1],mit=1;
	for(int i=2;i<=n;i++)
		if(mi.y>cow[i].y||(abs(mi.y-cow[i].y)<eps&&\
		mi.x>cow[i].x))
			mi=cow[i],mit=i;
	if(mit-1)swap(cow[1],cow[mit]);
	for(int i=2;i<=n;i++)cow[i].ang=Ang(1,i);
	sort(cow+2,cow+n+1);
	for(int i=3;i<=n;i++)
	{
		while((cow[st[top]].x-cow[st[top-1]].x)*(cow[i].y-\
		cow[st[top]].y)<(cow[st[top]].y-cow[st[top-1]].y)*\
		(cow[i].x-cow[st[top]].x))top--;
		st[++top]=i;
	}
	for(int i=1;i<=top;i++)ans+=dis(st[i],st[i%top+1]);
	printf("%.2lf",ans);
	return 0;
}
2022/8/6 09:47
加载中...