Luogu-3829 [SHOI2012]信用卡凸包

这道题的转化很巧妙，可以把信用卡四个角的圆心看做平面上的点来做凸包，\(ans\)就是凸包周长加上一个圆的周长

// luogu-judger-enable-o2

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=1e5+100;

const double Pi=3.14159265358979323846;

struct Point{

    double x,y;

    Point(double xx=0,double yy=0){

        x=xx,y=yy;

    }

    bool operator < (Point a) const{

        return x==a.x?y<a.y:x<a.x;

    }

    bool operator == (Point a) const{

        return x==a.x&&y==a.y;

    }

}a[maxn],b[maxn],c;

struct Vector{

    double x,y;

    Vector(double xx=0,double yy=0){

        x=xx,y=yy;

    }

}zhy[4];

int dcmp(double x){return fabs(x)<1e-9?0:(x>0?1:-1);}

Vector operator - (Point a,Point b){return Vector(a.x-b.x,a.y-b.y);}

Point operator + (Point a,Vector b){return Point(a.x+b.x,a.y+b.y);}

double operator * (Vector a,Vector b){return a.x*b.y-a.y*b.x;}

Vector rotate(Vector a,double p){return Vector(a.x*cos(p)-a.y*sin(p),a.x*sin(p)+a.y*cos(p));}

double dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}

double len(Vector a){return sqrt(dot(a,a));}

int n,m,tot;

double r,du;

void tb(Point *p,int n,Point *q,int &m){

    sort(p+1,p+n+1);

    q[m=1]=p[1];

    if(n==1) return;

    for(int i=2;i<=n;i++){

        while(m>1&&dcmp((q[m]-q[m-1])*(p[i]-q[m-1]))<=0)

            m--;

        q[++m]=p[i];

    }

    int k=m;

    for(int i=n-1;i>=1;i--){

        while(m>k&&dcmp((q[m]-q[m-1])*(p[i]-q[m-1]))<=0)

            m--;

        q[++m]=p[i];

    }

    m--;

}

double C(Point *p,int n){

    if(n==1) return 0;

    double tot=0;

    for(int i=1;i<n;i++)

        tot+=len(p[i+1]-p[i]);

    return tot+len(p[n]-p[1]);

}

int main(){

    scanf("%d",&m);

    scanf("%lf%lf%lf",&zhy[0].y,&zhy[0].x,&r);

    zhy[0].x/=2,zhy[0].y/=2;

    zhy[0].x-=r,zhy[0].y-=r;

    zhy[1]=zhy[2]=zhy[3]=zhy[0];

    zhy[1].x*=-1,zhy[2].x*=-1,zhy[2].y*=-1,zhy[3].y*=-1;

    for(int i=1;i<=m;i++){

        scanf("%lf%lf%lf",&c.x,&c.y,&du);

        for(int j=0;j<4;j++)

            a[++tot]=c+rotate(zhy[j],du);

    }

    tb(a,tot,b,n);

    double ans=C(b,n);

    ans=ans+2*Pi*r;

    printf("%.2lf\n",ans);

    return 0;

}

巴特西

Luogu-3829 [SHOI2012]信用卡凸包

最新文章

热门文章