社区讨论

蒟蒻刚学凸包,求dalao帮助qaq

P2742【模板】二维凸包 / [USACO5.1] 圈奶牛Fencing the Cows参与者 5已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@mi7pgs2t
此快照首次捕获于
2025/11/21 01:28
4 个月前
此快照最后确认于
2025/11/21 01:28
4 个月前
查看原帖
RT
CPP
#include <bits/stdc++.h>
using namespace std;
struct node
{
	double x,y;
}p[100010],s[100010];
int top,n;
bool cmp(node a,node b)
{
	double A=atan2((a.y-p[1].y),(a.x-p[1].x));
	double B=atan2((b.y-p[1].y),(b.x-p[1].x));
	if(A!=B)
	{
		return A<B;
	}
	else
	{
		return a.x<b.x;
	}
}
double cross(node a,node b,node c)
{
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
void get()
{
	p[0]=(node){0x3f3f3f3f,0x3f3f3f3f};
	int k;
	for(int i=1;i<=n;i++)
	{
		if(p[0].y>p[i].y||(p[0].y==p[i].y&&p[0].x>p[i].x))
		{
			p[0]=p[i];
			k=1;
		}
	}
	swap(p[k],p[1]);
	sort(p+2,p+n+1,cmp);
	s[0]=p[1],s[1]=p[2],top=1;
	for(int i=3;i<=n;)
	{
		if(top&&cross(s[top-1],p[i],s[top])>=0)
		{
			top--;
		}
		else
		{
			s[++top]=p[i++];
		}
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%lf%lf",&p[i].x,&p[i].y);
	}
	get();
	double ans=0.0;
	for(int i=1;i<=top;i++)
	{
		ans+=sqrt((s[i].x-s[i-1].x)*(s[i].x-s[i-1].x)+(s[i].y-s[i-1].y)*(s[i].y-s[i-1].y));
	}
	ans+=sqrt((s[top].x-s[0].x)*(s[top].x-s[0].x)+(s[top].y-s[0].y)*(s[top].y-s[0].y));
	printf("%.2lf",ans);
}

回复

6 条回复,欢迎继续交流。

正在加载回复...