社区讨论

求助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 条回复,欢迎继续交流。

正在加载回复...