http://172.20.6.3/Problem_Show.asp?id=1502
这种题用了快一天才写出来也是真的辣鸡。主要思路就是计算一下被挡住的弧度然后对弧度进行贪心。
最开始比较困扰的是求弧度值及其起始位置的部分，弧度值很好求，位置有点恶心，我的起始位置设置的是圆的十二点方向顺时针到起始位置的弧度值，然后我分了四种情况讨论（因为遮挡的方向有两种不同情况，遮挡部分弧度值与180度的关系又是两种情况），应该是有更简单的方法的，但是我只能想出来这种了。。。
代码
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 #include<iostream> 6 using namespace std; 7 const int maxn=1010; 8 const double eps=0.0000001; 9 long long n; 10 double r[maxn]={},x[maxn]={},y[maxn]={}; 11 struct nod{ 12 double id,v; 13 }e[maxn]; 14 int tot; 15 bool mmp(nod aa,nod bb){ 16 return aa.id<bb.id; 17 } 18 double getit(int i){ 19 tot=0;double cnt=0; 20 for(int j=n;j>i;j--){ 21 double w=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); 22 if(r[i]+r[j]-w<=0||r[i]-r[j]-w>=0)continue; 23 if(r[j]-r[i]-w>=0) return 0; 24 25 double z=(r[i]*r[i]-r[j]*r[j]+w*w)/(2*w); 26 double h=acos(z/r[i])*2; 27 28 double xx=x[i]+(x[j]-x[i])/w*z,yy=y[i]+(y[j]-y[i])/w*z; 29 double w1=sqrt((x[i]-xx)*(x[i]-xx)+(y[i]+z-yy)*(y[i]+z-yy)); 30 double h2=asin(w1/2/z)*2; 31 if(xx<x[i]){ 32 if(h2<0)h2=-h2; 33 else if(h2>0) h2=2*M_PI-h2; } 34 else if (xx>x[i]){if(h2<0) h2=2*M_PI+h2;} 35 h2=h2-h/2; 36 if(h2<0)h2+=2*M_PI; 37 h=h2+h; 38 if(h>2*M_PI){ 39 e[++tot].id=h2;e[tot].v=2*M_PI; 40 e[++tot].id=0;e[tot].v=h-2*M_PI; 41 }else{e[++tot].id=h2;e[tot].v=h;} 42 } 43 sort(e+1,e+1+tot,mmp); 44 double ll=0.0,rr=0.0; 45 for(int j=1;j<=tot;j++){ 46 if(e[j].id-rr<0){ 47 if(e[j].v-rr>0){ 48 rr=e[j].v; 49 } 50 } 51 else if(e[j].v-rr>0){ 52 cnt+=rr-ll; 53 rr=e[j].v;ll=e[j].id; 54 } 55 } 56 cnt+=rr-ll; 57 return r[i]*(M_PI*2-cnt); 58 } 59 int main(){ 60 //freopen("wtf.in","r",stdin); 61 scanf("%d",&n); 62 for(int i=1;i<=n;i++){ 63 scanf("%lf%lf%lf",&r[i],&x[i],&y[i]); 64 }double ans=0; 65 for(int i=n;i>=1;i--){ 66 ans+=getit(i); 67 }printf("%.3f ",ans); 68 return 0; 69 }