社区讨论
蒟蒻刚学凸包,求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 条回复,欢迎继续交流。
正在加载回复...