社区讨论
求助graham算法,错得五颜六色
P2742【模板】二维凸包 / [USACO5.1] 圈奶牛Fencing the Cows参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lo2khmgt
- 此快照首次捕获于
- 2023/10/23 15:19 2 年前
- 此快照最后确认于
- 2023/10/23 15:19 2 年前
CPP
#include <bits/stdc++.h>
using namespace std;
const int MAXN=100005;
struct Point{
double x,y;
}cow[MAXN];
double ans;
int n,pre;
int st[MAXN],top;
int lowx,pos;
double chakun(Point xx,Point yy,Point cc){
return ((xx.x-cc.x)*(yy.y-cc.y))-((xx.y-cc.y)*(yy.x-cc.x));
}
double distance(Point xx,Point yy){
return sqrt((xx.x-yy.x)*(xx.x-yy.x)+(xx.y-yy.y)*(xx.y-yy.y));
}
bool cmp(Point xx,Point yy){
double tmp=chakun(xx,yy,cow[1]);
if(tmp==0) return xx.x<yy.x;
else if(tmp>0) return 1;
return 0;
}
void swap(Point xx,Point yy){
double tmpx=xx.x;
double tmpy=xx.y;
xx.x=yy.x,xx.y=yy.y;
yy.x=tmpx,yy.y=tmpy;
}
void input(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lf%lf",&cow[i].x,&cow[i].y);
if(cow[i].x<cow[pos].x){
pos=i;
lowx=cow[i].x;
}
}
swap(cow[1],cow[pos]);
sort(cow+2,cow+1+n,cmp);
}
void graham(){
st[++top]=1;
for(int i=2;i<=n;i++){
while(top>1&&chakun(cow[top],cow[i],cow[top-1])<0) top--;
st[++top]=i;
}
st[++top]=1;
for(int i=1;i<=top-1;i++){
ans+=distance(cow[st[i]],cow[st[i+1]]);
}
}
void output(){
printf("%.2lf\n",ans);
}
int main()
{
input();
graham();
output();
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...