1 条题解

  • 0
    @ 2023-11-1 9:32:12

    容易发现是圆心的凸包再加上一个圆的周长。

    #include<bits/stdc++.h>
    using namespace std;
    const int N=1e4+5;
    const int dx[4]={1,-1,-1,1};
    const int dy[4]={1,1,-1,-1};
    const double Pi=acos(-1);
    struct point{
    	double x,y;
    }p[4*N],sta[4*N];
    double cross(point a,point b,point c){
    	return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
    }
    double dis(point a,point b){
    	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    }
    int len,top=0;
    bool cmp(point n1,point n2){
    	if(n1.x!=n2.x)return n1.x<n2.x;
    	return n1.y<n2.y;
    }
    double Andrew(){
    	sort(p+1,p+len+1,cmp);
    	for(int i=1;i<=len;i++){
    		while(top>1&&cross(sta[top-1],sta[top],p[i])<=0)top--;
    		sta[++top]=p[i];
    	}
    	int t=top;
    	for(int i=len-1;i>=1;i--){
    		while(top>t&&cross(sta[top-1],sta[top],p[i])<=0)top--;
    		sta[++top]=p[i];
    	}
    	double res=0;
    	for(int i=2;i<=top;i++){
    		res=res+dis(sta[i-1],sta[i]);
    	}
    	return res;
    }
    double getx(double x,double y,double rad){
    	return x*cos(rad)-y*sin(rad);
    }
    double gety(double x,double y,double rad){
    	return x*sin(rad)+y*cos(rad);
    }
    int main(){
    	int n;scanf("%d",&n);
    	double a,b,r;scanf("%lf%lf%lf",&a,&b,&r);
    	a=a/2-r,b=b/2-r;
    	for(int i=1;i<=n;i++){
    		double x,y,rad;
    		scanf("%lf%lf%lf",&x,&y,&rad);
    		for(int j=0;j<4;j++){
    			double tx=getx(b*dx[j],a*dy[j],rad);
    			double ty=gety(b*dx[j],a*dy[j],rad);
    			p[++len]={x+tx,y+ty};
    		}
    	}
    	printf("%.2lf",Andrew()+2*Pi*r);
    	return 0;
    }
    
    • 1

    信息

    ID
    2829
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    (无)
    递交数
    17
    已通过
    5
    上传者