覆盖距离AsiaHatyai-2012 & LA 6144 - Radiation 二分搜索-白红宇

覆盖距离AsiaHatyai-2012 & LA 6144 - Radiation 二分搜索

阅读量：6683 次

发布时间：2019-06-25

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

发一下牢骚和主题无关：

队内赛做的一道题..第一个关键是题意的掌控...意思是个每nuclear plant可以在其R范围内发放护保设备..如果一个点被一个nuclear plant覆盖就拿一个设备..如果被两个覆盖拿两个设备..没有被任何的覆盖..领不到设备...拿了两个设备的把过剩设备给没有设备的..问终究有多少人依然是没有设备的...

由于两个nuclear plant以及有所的点都是牢固的..所以可以先把有所点到plant A 的距离和plant B的距离算出来..序排别分存在两个组数中...对于前当讯问R1,R2..可用二分查找速快得出有多少点被A覆盖..多少点被B覆盖...相加记为sum....那么总人数N-sum既是最后也拿不到设备的人数..注意..有可能N-sum<0..所以输出时max(0,N-sum)...

Program:

每日一道理

生活的无奈，有时并不源于自我，别人无心的筑就，那是一种阴差阳错。生活本就是矛盾的，白天与黑夜间的距离，春夏秋冬之间的轮回，于是有了挑剔的喜爱，让无奈加上了喜悦的等待。

//https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=585&page=show_problem&problem=4155#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #define ll long long #define oo 1000000001#define MAXN 200002using namespace std; struct node1{ int x,y;}point[MAXN],a,b; int d1[MAXN],d2[MAXN],n;int main(){ // freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); int i,q,R1,R2,l,r,mid,sum,t=0; while (~scanf("%d",&n)) { if (!n) break; printf("Case %d:\n",++t); for (i=1;i<=n;i++) scanf("%d%d",&point[i].x,&point[i].y); scanf("%d%d%d%d%d",&a.x,&a.y,&b.x,&b.y,&q); for (i=1;i<=n;i++) { d1[i]=(point[i].x-a.x)*(point[i].x-a.x)+(point[i].y-a.y)*(point[i].y-a.y); d2[i]=(point[i].x-b.x)*(point[i].x-b.x)+(point[i].y-b.y)*(point[i].y-b.y); } sort(d1+1,d1+1+n); sort(d2+1,d2+1+n); while (q--) { scanf("%d%d",&R1,&R2); R1*=R1; R2*=R2; l=0; r=n+1; while (r-l>1) { mid=(r+l)/2; if (d1[mid]<=R1) l=mid; else r=mid; } sum=l; l=0; r=n+1; while (r-l>1) { mid=(r+l)/2; if (d2[mid]<=R2) l=mid; else r=mid; } sum+=l; printf("%d\n",max(n-sum,0)); } } return 0;}

文章结束给大家分享下程序员的一些笑话语录：腾讯总舵主马化腾，有人曾经戏称如果在Z国选举总统，马化腾一定当选，因为只要QQ来一个弹窗”投马总，送Q币”即可。

转载地址：http://zbxao.baihongyu.com/

你可能感兴趣的文章