Gym - 101673:B Craters (几何，求凸包)

题意：给定几个圆，求最短的围合，把这几个包围起来，而且到圆的距离都不小于10.

思路：把每个圆的半径+10，边等分5000份，然后求凸包即可。

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
typedef long long ll;
const double inf=1e200;
const double eps=1e-12;
const double pi=4*atan(1.0);
int dcmp(double x){ return fabs(x)<eps?0:(x<0?-1:1);}
struct point{
    double x,y;
    point(double a=0,double b=0):x(a),y(b){}
};
point operator +(point A,point B) { return point(A.x+B.x,A.y+B.y);}
point operator -(point A,point B) { return point(A.x-B.x,A.y-B.y);}
point operator *(point A,double p){ return point(A.x*p,A.y*p);}
point operator /(point A,double p){ return point(A.x/p,A.y/p);}
point rotate(point A,double rad){
    return point(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
}
bool operator ==(const point& a,const point& b) { 
     return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
}
double dot(point A,point B){ return A.x*B.x+A.y*B.y;}
double det(point A,point B){ return A.x*B.y-A.y*B.x;}
double det(point O,point A,point B){ return det(A-O,B-O);}
double length(point A){ return sqrt(dot(A,A));}
double angle(point A,point B){ return acos(dot(A,B)/length(A)/length(B));}
double area(vector<point>p){
    double ans=0; int sz=p.size();
    for(int i=1;i<sz-1;i++) ans+=det(p[i]-p[0],p[i+1]-p[0]);
    return ans/2.0;
}
double seg(point O,point A,point B){
    if(dcmp(B.x-A.x)==0) return (O.y-A.y)/(B.y-A.y);
    return (O.x-A.x)/(B.x-A.x);
}

pair<double,int>s[110*60]; 
double polyunion(vector<point>*p,int N){ //有多个才加* 
    double res=0;
    for(int i=0;i<N;i++){
        int sz=p[i].size();
        for(int j=0;j<sz;j++){
            int m=0;
            s[++m]=mp(0,0);
            s[++m]=mp(1,0);
            point a=p[i][j],b=p[i][(j+1)%sz];
            for(int k=0;k<N;k++){
                if(i!=k){
                    int sz2=p[k].size();
                    for(int ii=0;ii<sz2;ii++){
                        point c=p[k][ii],d=p[k][(ii+1)%sz2];
                        int c1=dcmp(det(b-a,c-a));
                        int c2=dcmp(det(b-a,d-a));
                        if(c1==0&&c2==0){
                            if(dcmp(dot(b-a,d-c))){
                                s[++m]=mp(seg(c,a,b),1);
                                s[++m]=mp(seg(c,a,b),-1);
                            }
                        }
                        else{
                            double s1=det(d-c,a-c);
                            double s2=det(d-c,b-c);
                            if(c1>=0&&c2<0) s[++m]=mp(s1/(s1-s2),1);
                            else if(c1<0&&c2>=0) s[++m]=mp(s1/(s1-s2),-1);
                        }
                    }
                }    
            }
            sort(s+1,s+m+1);
            double pre=min(max(s[1].first,0.0),1.0),now,sum=0;
            int cov=s[0].second;
            for(int j=2;j<=m;j++){
                now=min(max(s[j].first,0.0),1.0);
                if(!cov) sum+=now-pre;
                cov+=s[j].second;
                pre=now;
            }
            res+=det(a,b)*sum;
        }
    }
    return res/2;
}
bool cmp(point a,point b){ return a.x==b.x?a.y<b.y:a.x<b.x; }
void convexhull(point *a,int n,point *ch,int &top)
{
    sort(a+1,a+n+1,cmp);
    top=0;
    for(int i=1;i<=n;i++){
        while(top>=2&&det(ch[top-1],ch[top],a[i])<=0) top--;
        ch[++top]=a[i];
    }
    int ttop=top;
    for(int i=n-1;i>=1;i--){
        while(top>ttop&&det(ch[top-1],ch[top],a[i])<=0) top--;
        ch[++top]=a[i];
    }
}
point ch[2000000],p[2000000]; vector<point>pp[110];
int main()
{
    int N,i,j,tot=0,top; double ans,one=pi/2500,x,y,r;
    scanf("%d",&N);
    for(i=1;i<=N;i++){
        scanf("%lf%lf%lf",&x,&y,&r); r+=10; 
        for(j=1;j<=5000;j++){
            tot++; p[tot].x=x+r*cos(one*j); p[tot].y=y+r*sin(one*j);
        }
    }
    convexhull(p,tot,ch,top);
    for(i=1;i<top;i++) ans+=length(ch[i]-ch[i+1]);
    printf("%.10lf\n",ans);
    return 0;
}