Codeforces Round #357 (Div. 2) E 计算几何-白红宇

Codeforces Round #357 (Div. 2) E 计算几何

阅读量：6712 次

发布时间：2019-06-25

本文共 2085 字，大约阅读时间需要 6 分钟。

传说中做cf不补题等于没做于是第一次补...这次的cf没有做出来DE D题的描述神奇到现在也没有看懂于是只补了E

每次div2都是hack前2~3题终于打出一次hack后的三题了...希望以后能越来越好早日..至少变成蓝色名字吧:)

E题意有一个蟑螂人要打死它给出蟑螂的坐标速度人的瞄准时间再给出一些阴影(圆形且给出坐标与半径) 若蟑螂移动到阴影内会立即停下人不能打到阴影中的蟑螂问它不被打死的机率蟑螂的移动方向是随机的

需要注意的是蟑螂只会朝一个方向走直线

所以我们对于每一个阴影圆都判断一次能否走到如果能走到就计算角度这里利用atan来实现 atan(x,y) 返回的是平面直角坐标系上原点到x,y的线与x轴的夹角

需要注意的是在两个圆的相交到一定程度的时候需要进行判断是否到了最大值在到达最大值之后角度会减小这时候应当取最大的角度

对于每一个可以到达的阴影我们都可以得出一个角度区间最后我们应当对每个区间进行合并

在angle+-ang之后可能产生<-pi or >pi的角度这时候我们进行分割分成两份一份在最左一份在最右

排个序再进行判断就好

在补这道题的时候 acos的时候写错了字母...一路跑到了test79才wa掉...真是..doubility

#include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #include
           
            using namespace std;double x0,yy,v,t;int n;double pi;struct node{ double x,y,r;};node a[100050];int w;struct no{ double k1,k2;};no b[100050];double dis(double x1,double y1,double x2,double y2){ return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}double r;void check(int x){ if(dis(a[x].x,a[x].y,x0,yy)>=(r+a[x].r)) return ; double d=dis(a[x].x,a[x].y,x0,yy); /// -pi
            
             
              =-pi-0.000000000001&&ar<=pi+0.000000000001){ w++; b[w].k1=al; b[w].k2=ar; } else if(al<-pi-0.000000000001){ w++; b[w].k1=-pi; b[w].k2=ar; w++; b[w].k1=pi+(al+pi); b[w].k2=pi; } else if(ar>pi+0.000000000001){ w++; b[w].k1=al; b[w].k2=pi; w++; b[w].k1=-pi; b[w].k2=-pi+(ar-pi); } return ;}int cmp(no a,no b){ return a.k1
              
               b.k2;}int main(){while(cin>>x0>>yy>>v>>t){ pi=acos(-1); cin>>n; bool ok=false; for(int i=1;i<=n;i++){ scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].r); if((x0-a[i].x)*(x0-a[i].x)+(yy-a[i].y)*(yy-a[i].y)<=a[i].r*a[i].r){ ok=true; } } r=v*t; if(ok==true){ printf("1.00000000000\n"); } else { w=0; for(int i=1;i<=n;i++){ check(i); } if(w==0) { printf("0.00000000000\n"); } else { sort(b+1,b+1+w,cmp); double ans=0; double q=-pi; for(int i=1;i<=w;i++) { double l=b[i].k1; double r=b[i].k2; if(r>q){ double ll; if(l>q){ ll=l; } else { ll=q; } if(r-ll>0) ans+=(r-ll); q=r; } else continue; } printf("%.11f\n",ans/(2*pi)); } }}}

转载于:https://www.cnblogs.com/rayrayrainrain/p/5592043.html

你可能感兴趣的文章