二维凸包

一粒夸克 · 2021-04-28 11:54:05 · 个人记录

模板

这将是我做的最后一道计算几何

【模板】二维凸包

只会写最简单最快的Andrew

尝试用斜率写了一下，才明白他们为什么要用向量

因为 x 相同时，不好处理

#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
    double x,y;
    inline bool operator <(const node &b)const{
        if(x==b.x)return y<b.y;
        return x<b.x;
    }
}d[100005];
int stk[100005],top;
inline double dis(int i,int j){
    return sqrt((d[i].x-d[j].x)*(d[i].x-d[j].x)+(d[i].y-d[j].y)*(d[i].y-d[j].y));
}
inline double k(int i,int j){
    return (d[i].y-d[j].y)/(d[i].x-d[j].x);
}
void andrew(){
    sort(d,d+n);
    stk[top++]=0;stk[top++]=1;
    for(int i=2;i<n;i++){
        while(k(i,stk[top-1])<k(stk[top-1],stk[top-2])){
            if(top==1)break;top--;
        }
        stk[top++]=i;
    }
    int tmp=top;
    stk[top++]=n-1;stk[top++]=n-2;
    for(int i=n-3;i>=0;i--){
        printf("%d %d %d %lf %lf\n",i,stk[top-1],stk[top-2],k(i,stk[top-1]),k(stk[top-1],stk[top-2]));
        while(k(i,stk[top-1])<k(stk[top-1],stk[top-2])){
            if(top==tmp+1)break;top--;
        }
        stk[top++]=i;
    }

}
double ans;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%lf%lf",&d[i].x,&d[i].y);
    andrew();
    for(int i=0;i<top-1;i++)ans+=dis(stk[i],stk[i+1]);
    for(int i=0;i<top;i++)printf("%d ",stk[i]);
    putchar('\n');
    printf("%.2lf",ans);

    return 0;
} 

对于数据：

4
4 8
4 12
5 9.3
7 8

结果为：

1 2 3 -2.700000 -0.650000
0 1 3 -inf -1.333333
0 3 3 0 
6.00

正确答案是 12

少了个点 1 ，结果就比答案小了 6

如果把 k(i,stk[top-1]) 改成 k(stk[top-1],i)

1 2 3 -2.700000 -0.650000
0 1 3 -inf -1.333333
0 3 3 1 0 
12.00