凸包模板


int sgn(double x){
    if (x>eps)return 1;
    if (x<-eps)return -1;
    return 0;
}
struct vec{
    double x,y;
    vec(){x=y=0;}
    vec(double _x,double _y){x=_x,y=_y;}
    vec operator + (vec v){return vec(x+v.x,y+v.y);}
    vec operator - (vec v){return vec(x-v.x,y-v.y);}
    vec operator * (double v){return vec(x*v,y*v);}
    vec operator / (double v){return vec(x/v,y/v);}
    double operator * (vec v){return x*v.x+y*v.y;}
};
bool cmpXY(vec a,vec b){
    if (sgn(a.x-b.x))return a.x<b.x;
    return a.y<b.y;
}
double cross(vec a ,vec b){
    return a.x*b.y-a.y*b.x;
}
int convec_hull(vec*v,int n,vec* z){// 输入  数据大小  答案
    sort(v,v+n,cmpXY);
    int m = 0;
    for(int i=0;i<n;i++){
        while (m>1 && cross(z[m-1]-z[m-2],v[i]-z[m-2])<=0)--m;
        z[m++] = v[i];
    }
    int k = m;
    for(int i=n - 2;i>=0;--i) {
        while( m > k && cross(z[m-1]-z[m-2],v[i]-z[m-2]) <= 0 ) --m;
        z[m++] = v[i];
    }
    if(n>1)--m;
    return m;
}

板子题:
P2742
给n 个点,求形成的凸包的周长。
样例1

4
4 8
4 12
5 9.3
7 8

输出
12.00

#include<bits/stdc++.h>
using namespace std;
#define N 1000010
const int mod = 1000000007;
const int inf = 1000000007;
const double eps = 1e-9;
void in(int &x){
    x=0;char c=getchar();
    int y=1;
    while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    x*=y;
}
void o(int x){
    if(x<0){x=-x;putchar('-');}
    if(x>9)o(x/10);
    putchar(x%10+'0');
}
int sgn(double x){
    if (x>eps)return 1;
    if (x<-eps)return -1;
    return 0;
}
struct vec{
    double x,y;
    vec(){x=y=0;}
    vec(double _x,double _y){x=_x,y=_y;}
    vec operator + (vec v){return vec(x+v.x,y+v.y);}
    vec operator - (vec v){return vec(x-v.x,y-v.y);}
    vec operator * (double v){return vec(x*v,y*v);}
    vec operator / (double v){return vec(x/v,y/v);}
    double operator * (vec v){return x*v.x+y*v.y;}
};
bool cmpXY(vec a,vec b){
    if (sgn(a.x-b.x))return a.x<b.x;
    return a.y<b.y;
}
double cross(vec a ,vec b){
    return a.x*b.y-a.y*b.x;
}
int convec_hull(vec*v,int n,vec* z){
    sort(v,v+n,cmpXY);
    int m = 0;
    for(int i=0;i<n;i++){
        while (m>1 && cross(z[m-1]-z[m-2],v[i]-z[m-2])<=0)--m;
        z[m++] = v[i];
    }
    int k = m;
    for(int i=n - 2;i>=0;--i) {
        while( m > k && cross(z[m-1]-z[m-2],v[i]-z[m-2]) <= 0 ) --m;
        z[m++] = v[i];
    }
    if(n>1)--m;
    return m;
}
double Length(vec x){
    return sqrt(x.x*x.x+x.y*x.y);
}
int n;
vec a[N],ans[N];
signed main(){
    in(n);
    for(int i=0;i<n;i++){
        cin>>a[i].x>>a[i].y;
    }
    int m=convec_hull(a,n,ans);
    double ANS=0.0;
    for(int i=0;i<m;i++){
        ANS += Length(ans[i+1]-ans[i]);
    }
    printf("%.2lf\n",ANS);
    return 0;
}
上一篇:前端工程环境变量设置方法


下一篇:论文阅读笔记(六十三)【ACMMM2017】:Adversarial Cross-Modal Retrieval