题意: 平面里给出M个三角形, N个圆形, 图形之间两两不相交, 求一个把这些图形围起来周长最小的一个圈的周长~
分析:把三角形顶点分解成点, 对圆形求可能的切点:1.点和圆的两个切点, 2.圆和圆的外公切线切点。
然后对所有点求凸包, 处理周长的时候, 如果凸包上两个相邻点在同一个圆上, 则求相应的弧长~。此方法有个trick: 只有一个圆的时候需要特殊处理.
#include<cstdio> #include<iostream> #include<cstdlib> #include<algorithm> #include<cmath> #include<string> #include<cstring> #include<set> #include<map> #include<list> #include<queue> #include<vector> #define tree int o,int l,int r #define lson o<<1,l,mid #define rson o<<1|1,mid+1,r #define lo o<<1 #define ro o<<1|1 #define ULL unsigned long long #define LL long long #define UI unsigned int #define inf 0x7fffffff #define eps 1e-7 using namespace std; const double pi=acos(-1.0); int m,n,t; struct Point { double x,y; int id; Point(double x=0,double y=0,int id_=-1):x(x),y(y) {} }; Point readpoint() { double x,y; scanf("%lf%lf",&x,&y); return Point(x,y); } typedef Point Vector;//类似 int dcmp(double d)//返回符号 { if(fabs(d)<eps)return 0; return d<0?-1:1; } Vector operator+(Vector a,Vector b) { return Vector(a.x+b.x,a.y+b.y); } Vector operator-(Vector a,Vector b) { return Vector(a.x-b.x,a.y-b.y); } Vector operator*(Vector a,double p) { return Vector(a.x*p,a.y*p); } Vector operator/(Vector a,double p) { return Vector(a.x/p,a.y/p); } bool operator<(Vector a,Vector b) { return dcmp(a.x-b.x)<0||(dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)<0); } bool operator==(Vector a,Vector b)//double类型不能直接比较! { return (dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0); } double dot(Vector a,Vector b)//点积,可能是负数 { return a.x*b.x+a.y*b.y; } double cross(Vector a,Vector b)//叉积,可能是负数 { return a.x*b.y-b.x*a.y; } double operator * (Point a,Point b)//叉积,可能是负数,运算符重载! { return a.x*b.y-b.x*a.y; } double length(Vector a) { return sqrt(dot(a,a)); } double angle(Vector a,Vector b)//[0,pi] { return acos(dot(a,b)/length(a)/length(b)); } struct Circle { Point c; double r; Circle() {} Circle(Point cc,double rr):c(cc),r(rr) {} Point point(double rad) { return Point(c.x+r*cos(rad),c.y+r*sin(rad)); } }; void readcircle(Circle &c) { scanf("%lf%lf%lf",&c.c.x,&c.c.y,&c.r); } int pcl(Point p,Circle o,Vector* v)//点到圆的切线的切点,考虑不同情况 { Point u=p-o.c; double d=length(u); double a=atan2(u.y,u.x); if(d<o.r)return 0;//园内 else if(dcmp(d-o.r)==0)//圆上 { v[0]=o.point(a); return 1; } else { double ang=acos(o.r/d); v[0]=o.point(a+ang); v[1]=o.point(a-ang); return 2; } } int ccl(Circle c1,Circle c2,Point *a,Point *b) { int cnt=0; if(dcmp(c1.r-c2.r)<0)//保证结果为正值 { swap(c1,c2); swap(a,b); } Vector u=c2.c-c1.c; double d=length(u); double ang=atan2(u.y,u.x); //有外公切线 double g=acos((c1.r-c2.r)/d); a[cnt]=c1.point(ang+g); b[cnt]=c2.point(ang+g); cnt++; a[cnt]=c1.point(ang-g); b[cnt]=c2.point(ang-g); cnt++; return cnt; } double arc(Point a,Point b,Circle c)//a,b逆时针穿过圆c外面的的圆弧长 { Point u=a-c.c,v=b-c.c; double ang=angle(u,v); if(cross(u,v)>eps) return ang*c.r; return (pi*2.0-ang)*c.r; } int tubao(Point p[],int n,Point *ch,int &w)//(凸包)p中不能有重复的点,p会变,可以共线时“<=”改为“<” { int m=0; sort(p,p+n);//必须排序 n=unique(p,p+n)-p; for(int i=0; i<n; i++) { while(m>1&&dcmp(cross(ch[m-1]-ch[m-2],p[i]-ch[m-2]))<=0)//注意:可以共线时“<=”改为“<” m--; ch[m++]=p[i]; } int k=m; w=m-1;//中间的位置 for(int i=n-2; i>=0; i--) { while(m>k&&dcmp(cross(ch[m-1]-ch[m-2],p[i]-ch[m-2]))<=0)//注意:可以共线时“<=”改为“<” m--; ch[m++]=p[i]; } if(n>1) m--;//特殊情况 return m; } #define N 400000 Point p[N]; Point ch[N]; Circle c[N]; Point a[10],b[10]; Point q[N]; void write(Point p) { printf("(%lf,%lf)",p.x,p.y); } int main() { #ifndef ONLINE_JUDGE freopen("ex.in","r",stdin); #endif while(scanf("%d%d",&n,&m)==2) { for(int i=0; i<n; i++) readcircle(c[i]); for(int i=0; i<m*3; i++) { p[i]=readpoint(); p[i].id=-i*3-1; } if(n==1&&!m)//没有交点,WA { printf("%.9lf ",pi*2*c[0].r);; continue; } swap(n,m); n*=3; for(int i=n-1; i>=0; i--) for(int j=0; j<m; j++) { Point v[2]; int num=pcl(p[i],c[j],v); for(int k=0; k<num; k++) { p[n++]=v[k]; p[n-1].id=j; } } for(int j=0; j<m; j++) for(int i=j+1; i<m; i++) { int num=ccl(c[j],c[i],a,b); for(int k=0; k<num; k++) { p[n++]=a[k]; p[n-1].id=j; p[n++]=b[k]; p[n-1].id=i; } } int nn; n=tubao(p,n,ch,nn); memcpy(p,ch,sizeof(ch)); double len=0.0; p[n]=p[0]; for(int i=0; i<n; i++) { if(p[i].id==p[i+1].id) { len+=arc(p[i],p[i+1],c[p[i].id]); } else { len+=length(p[i]-p[i+1]); } } printf("%.9lf ",len); } return 0; }