为按照极角，转化为线段覆盖问题。
这题有个特别混蛋的trick，就是后掉落的把先掉落的完全覆盖了，我就没考虑这个，无限wa啊！！
View Code
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 #include <cstdlib> 6 #include <cmath> 7 #include <vector> 8 9 #define N 1111 10 #define PI 3.14159265358979323846 11 #define EPS 1e-7 12 13 using namespace std; 14 15 struct PO 16 { 17 double x,y,r; 18 void prt() {printf("%lf %lf\n",x,y);} 19 }p[N]; 20 21 struct V 22 { 23 int fg; double f; 24 }; 25 vector<V> v[N]; 26 27 int n; 28 double sum,ans; 29 bool vis[N]; 30 31 inline int dc(double x) 32 { 33 if(x>EPS) return 1; 34 else if(x<-EPS) return -1; 35 return 0; 36 } 37 38 inline bool cmp(const V &a,const V &b) 39 { 40 if(a.f==b.f) return a.fg>b.fg; 41 return a.f<b.f; 42 } 43 44 inline PO operator -(PO a,PO b) 45 { 46 a.x-=b.x; a.y-=b.y; 47 return a; 48 } 49 50 inline PO operator +(PO a,PO b) 51 { 52 a.x+=b.x; a.y+=b.y; 53 return a; 54 } 55 56 inline PO operator *(PO a,double k) 57 { 58 a.x*=k; a.y*=k; 59 return a; 60 } 61 62 inline PO operator /(PO a,double k) 63 { 64 a.x/=k; a.y/=k; 65 return a; 66 } 67 68 inline double getlen(const PO &a) 69 { 70 return sqrt(a.x*a.x+a.y*a.y); 71 } 72 73 inline double getdis(const PO &a,const PO &b) 74 { 75 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); 76 } 77 78 inline PO rotate(const PO &a,double sss,double ccc) 79 { 80 PO rt; 81 rt.x=a.x*ccc-a.y*sss; 82 rt.y=a.x*sss+a.y*ccc; 83 return rt; 84 } 85 86 inline void read() 87 { 88 scanf("%d",&n); 89 for(int i=1;i<=n;i++) 90 scanf("%lf%lf%lf",&p[i].r,&p[i].x,&p[i].y); 91 } 92 93 inline void getcpoint(const PO &a,const PO &b,PO &s,PO &t)//求圆的交点，a的逆时针方向的弧上的点 94 { 95 PO ab=b-a; 96 double d=getlen(ab); 97 double ccc=(b.r*b.r-d*d-a.r*a.r)/(-2.0*a.r*d); 98 double sss=sqrt(1.0-ccc*ccc); 99 ab=ab/d*a.r; 100 s=a+rotate(ab,-sss,ccc); 101 t=a+rotate(ab,sss,ccc); 102 } 103 104 inline void go() 105 { 106 PO a,b; V c; 107 double f1,f2; 108 for(int i=1;i<=n;i++) 109 for(int j=i+1;j<=n;j++) 110 { 111 double dis=getdis(p[i],p[j]); 112 if(dis+1e-10>p[i].r+p[j].r || p[j].r+1e-10<p[i].r&&dis-1e-10<p[i].r-p[j].r) continue; 113 if(p[i].r<p[j].r+1e-10&&dis-1e-10<p[j].r-p[i].r) {vis[i]=true; break;} 114 getcpoint(p[i],p[j],a,b); 115 f1=atan2(a.y-p[i].y,a.x-p[i].x); 116 f2=atan2(b.y-p[i].y,b.x-p[i].x); 117 if(f1>f2) 118 { 119 c.f=f1; c.fg=1; v[i].push_back(c); 120 c.f=PI; c.fg=-1; v[i].push_back(c); 121 c.f=-PI; c.fg=1; v[i].push_back(c); 122 c.f=f2; c.fg=-1; v[i].push_back(c); 123 } 124 else 125 { 126 c.f=f1; c.fg=1; v[i].push_back(c); 127 c.f=f2; c.fg=-1; v[i].push_back(c); 128 } 129 } 130 for(int i=1;i<=n;i++) 131 { 132 if(vis[i]) continue; 133 sum+=2*PI*p[i].r; 134 sort(v[i].begin(),v[i].end(),cmp); 135 int tmp=0; double last; 136 for(int j=0;j<v[i].size();j++) 137 { 138 tmp+=v[i][j].fg; 139 if(tmp==1&&v[i][j].fg==1) last=v[i][j].f; 140 else if(tmp==0&&v[i][j].fg==-1) ans+=(v[i][j].f-last)*p[i].r; 141 } 142 } 143 printf("%.3lf\n",sum-ans); 144 } 145 146 int main() 147 { 148 read(),go(); 149 return 0; 150 }