专栏文章
题解：P2742 [USACO5.1] 圈奶牛Fencing the Cows /【模板】二维凸包
P2742题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @minhgj40
- 此快照首次捕获于
- 2025/12/02 02:28 3 个月前
- 此快照最后确认于
- 2025/12/02 02:28 3 个月前
P2742 Andrew算法
题目传送门①前世记忆-凸包
在平面上能包含所有给定点的最小凸多边形叫做凸包。
本题就是让你求这个图形的周长。
本题就是让你求这个图形的周长。
②算法介绍
0.时间复杂度为 O(nlogn)。
1.先按 x 轴 y 轴排序。
2.我们把第一个点和最后一个点以上的部分叫做上凸壳,把两个点以下的部分叫下凸壳。
3.我们可以先算下凸壳再算上凸壳。
4.求下凸壳时,我们可以发现,相邻两条边居然是逆时针转的的,这样的化,我们就好求多了。在求的时候直接用单调栈。
看栈顶,栈顶下一个,和这个点是否满足这样的关系就可以了。
维护的时候就进栈的打上标记,离开栈的取消标记就行了。
5.更惊喜的是上凸壳也是这样的。
6.一个小技巧 两个向量叉积的结果是负的就是就是顺时针的,正的就是逆时针的(顺负逆正)。
向量 f 是由 (栈顶下一个)A 指向 (栈内的栈顶)B 的向量。
向量 g 是由 (栈内的栈顶)B 指向 (现在的这点)C 的向量。
向量f和向量g的叉积显然是负的。
向量 g 是由 (栈内的栈顶)B 指向 (现在的这点)C 的向量。
向量f和向量g的叉积显然是负的。
③结果计算
④思路证明
很显然,在模拟的时候不会有错。
⑤代码
CPP#include<bits/stdc++.h>
#define double long double
#define N 600100
using namespace std;
struct node{
double x,y;
node operator-(node a){
return {x-a.x,y-a.y};
}
}k[N];
long long n,top1=0,st[N],st1[N];
bool bj[N];
double ans=0;
double cross(node a,node b){//叉积
return a.x*b.y-a.y*b.x;
}
bool cmp(node a,node b){//按 x,y坐标排序
if(a.x==b.x)return a.y<b.y;
return a.x<b.x;
}
double js(node a,node b){//神秘公式
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>k[i].x>>k[i].y;
sort(k+1,k+1+n,cmp);
st[++top1]=1;
for(int i=2;i<=n;i++){//单调栈
while(top1>=2&&cross((node){k[st[top1]].x,k[st[top1]].y}-(node){k[st[top1-1]].x,k[st[top1-1]].y},(node){k[i].x,k[i].y}-(node){k[st[top1]].x,k[st[top1]].y})<0)
bj[st[top1--]]=0;
st[++top1]=i;
bj[i]=1;
}
for(int i=1;i<top1;i++){
ans+=js({k[st[i]].x,k[st[i]].y},{k[st[i+1]].x,k[st[i+1]].y});
}
st[top1=1]=n;
for(int i=n;i>=1;i--){
if(bj[i])continue;
while(top1>=2&&cross((node){k[st[top1]].x,k[st[top1]].y}-(node){k[st[top1-1]].x,k[st[top1-1]].y},(node){k[i].x,k[i].y}-(node){k[st[top1]].x,k[st[top1]].y})<0)
bj[st[top1--]]=0;
st[++top1]=i;
}
for(int i=1;i<top1;i++){
ans+=js({k[st[i]].x,k[st[i]].y},{k[st[i+1]].x,k[st[i+1]].y});
}
printf("%.2Lf\n",ans);
return 0;
}
相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...