首页 > 代码库 > bzoj1536: [POI2005]Akc- Special Forces Manoeuvres
bzoj1536: [POI2005]Akc- Special Forces Manoeuvres
Description
在一次军事行动中有一批空降兵要降落在沙漠中拆除炸弹. 空降兵按照预定的顺序跳伞并降落到指定的位置.一旦降落他们便呆在原地不动了. 每个空降兵都有一个生存半径. 如果炸弹与他的距离小于或等于这个生存半径的话,空降兵便会引爆炸弹导致死亡. 指挥官想尽量少的派出升降兵.但是在这个目标的前提是至少要能有1名伞兵活着回来.(无论炸弹在何处的情况下都如此). 我们可以假定沙漠抽象成一个二维平面,每个伞兵降落的地点都是这个平面上的一个整点.我们会给定伞兵降落的顺序,每个伞兵都不会不跳,即如果第i个伞兵在沙漠中着陆,那么他前面的所有伞兵肯定都已着陆.求指挥官至少要派出多少空降兵.
Input
第一行一个数n ( 2 <= n <= 2 000) – 空降兵的个数. 接下来n 行每行描述一个空降兵. 每个空降兵用三个整数: x, y 和 r ( -1000 <= x, y <= 1000, 1 <= r <= 5000). 表示空降兵在点(x, y) 着陆, 他的生存半径为 r.
Output
输出一行表示最少需要派出多少空降兵.如果所有的空降兵都有可能牺牲的话输出NIE (NO in Polish).
二分答案，判定时当且仅当所有圆的交严格为空为可行，判定时二分找一条平行y轴的直线使其过所有圆，若不存在这样的直线，或直线上不可能存在一点在所有圆内/上，则交集为空，具体实现见代码。
#include<cstdio>#include<cmath>typedef long double ld;const ld _0=1e-7;ld x[2007],y[2007],r[2007];void get(int id,ld X,ld&a,ld&b){ X-=x[id]; X=std::sqrt(r[id]*r[id]-X*X); a=y[id]-X-_0; b=y[id]+X+_0;}ld dis(int a,int b){ ld X=x[a]-x[b],Y=y[a]-y[b]; return sqrt(X*X+Y*Y);}ld cal(int a,int b){ return x[a]+(x[b]-x[a])*r[a]/dis(a,b);}bool chk(int n){ ld L=x[1]-r[1],R=x[1]+r[1],M; for(int i=2;i<=n;++i){ if(x[i]-r[i]<L)L=x[i]-r[i]; if(x[i]+r[i]>R)R=x[i]+r[i]; } while(1){ M=(L+R)/2; bool dl=0,dr=0; for(int i=1;i<=n;++i){ if(x[i]+r[i]<M)dl=1; if(x[i]-r[i]>M)dr=1; } if(dl){ if(dr)return 0; R=M; }else if(dr)L=M; else{ ld y1,y2,a1,a2; get(1,M,y1,y2); for(int i=2;i<=n;++i){ get(i,M,a1,a2); if(a1>y1)y1=a1; if(a2<y2)y2=a2; if(y1>y2){ for(int j=1;j<i;++j){ get(j,M,y1,y2); if(y1>a2||y2<a1){ if(dis(i,j)>r[i]+r[j]+_0)return 0; ld xm=cal(i,j); if(xm>R||xm<L)return 0; if(M<xm)L=M; else R=M; goto out; } } } } return 1; } out:; }}int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;++i)scanf("%llf%llf%llf",x+i,y+i,r+i),r[i]+=_0; if(chk(n))return puts("NIE"),0; int L=1,R=n,M; while(L<R){ M=L+R>>1; if(chk(M))L=M+1; else R=M; } return printf("%d",L),0;}
bzoj1536: [POI2005]Akc- Special Forces Manoeuvres
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。