1 条题解
-
0
容易发现是圆心的凸包再加上一个圆的周长。
#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
- 上传者