P1158 导弹拦截【洛谷算法习题】

P1158 导弹拦截网页链接P1158 导弹拦截题目描述经过11 1111年的韬光养晦某国研发出了一种新的导弹拦截系统凡是与它的距离不超过其工作半径的导弹都能够被它成功拦截。当工作半径为0 00时则能够拦截与它位置恰好相同的导弹。但该导弹拦截系统也存在这样的缺陷每套系统每天只能设定一次工作半径。而当天的使用代价就是所有系统工作半径的平方和。某天雷达捕捉到敌国的导弹来袭。由于该系统尚处于试验阶段所以只有两套系统投入工作。如果现在的要求是拦截所有的导弹请计算这一天的最小使用代价。输入格式第一行包含4 44个整数x 1 , y 1 , x 2 , y 2 x_1,y_1,x_2,y_2x1​,y1​,x2​,y2​每两个整数之间用一个空格隔开表示这两套导弹拦截系统的坐标分别为( x 1 , y 1 ) , ( x 2 , y 2 ) (x_1,y_1), (x_2,y_2)(x1​,y1​),(x2​,y2​)。第二行包含1 11个整数N NN表示有N NN颗导弹。接下来N NN行每行两个整数x , y x,yx,y中间用一个空格隔开表示一颗导弹的坐标( x , y ) (x,y)(x,y)。不同导弹的坐标可能相同。输出格式一个整数即当天的最小使用代价。输入输出样例 #1输入 #10 0 10 0 2 -3 3 10 0输出 #118输入输出样例 #2输入 #20 0 6 0 5 -4 -2 -2 3 4 0 6 -2 9 1输出 #230说明/提示两个点( x 1 , y 1 ) , ( x 2 , y 2 ) (x_1,y_1),(x_2,y_2)(x1​,y1​),(x2​,y2​)之间距离的平方是( x 1 − x 2 ) 2 ( y 1 − y 2 ) 2 (x_1-x_2)^2(y_1-y_2)^2(x1​−x2​)2(y1​−y2​)2。两套系统工作半径r 1 , r 2 r_1,r_2r1​,r2​的平方和是指r 1 , r 2 r_1,r_2r1​,r2​分别取平方后再求和即r 1 2 r 2 2 r_1^2r_2^2r12​r22​。样例 1 说明样例1 11中要拦截所有导弹在满足最小使用代价的前提下两套系统工作半径的平方分别为18 1818和0 00。样例 2 说明样例2 22中的导弹拦截系统和导弹所在的位置如下图所示。要拦截所有导弹在满足最小使用代价的前提下两套系统工作半径的平方分别为20 2020和10 1010。【数据范围】。对于10 % 10\%10%的数据N 1 N1N1。对于20 % 20\%20%的数据1 ≤ N ≤ 2 1\le N\le 21≤N≤2。对于40 % 40\%40%的数据1 ≤ N ≤ 100 1\le N\le 1001≤N≤100。对于70 % 70\%70%的数据1 ≤ N ≤ 1000 1\le N\le 10001≤N≤1000。对于100 % 100\%100%的数据1 ≤ N ≤ 10 5 1\le N\le 10^51≤N≤105且所有坐标分量的绝对值都不超过1000 10001000。NOIP2010 普及组 第三题解题思路本题核心是排序贪心枚举求解两套导弹拦截系统的最小代价。题目要求拦截所有导弹代价为两套系统半径的平方和因此无需开根号直接计算距离平方规避浮点误差。先算出每枚导弹到两个系统的距离平方将导弹按到系统1的距离平方升序排序。枚举分界点系统1覆盖前i枚导弹半径取第i枚的距离平方剩余导弹由系统2覆盖半径取剩余导弹的最大距离平方。遍历所有分界点计算平方和最小值同时考虑全由系统2覆盖的边界情况。算法时间复杂度O ( N log ⁡ N ) O(N\log N)O(NlogN)完美适配N ≤ 10 5 N≤10^5N≤105的大数据规模。总结核心逻辑按导弹到系统1的距离排序枚举系统1的覆盖范围系统2兜底剩余导弹求半径平方和最小值。关键操作计算距离平方、排序导弹、逆序遍历维护系统2最大半径、枚举最优解。效率保障排序线性遍历无浮点运算高效处理十万级数据量。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N2e510;constll p1e97;constll INF1e18;constll M1e610;structstu{ll x,y,dis1,dis2;}d[N];ll a1,b1,a2,b2,n,x,y,ans,cnt;lldist(ll a1,ll b1,ll a2,ll b2){returnpow(a1-a2,2)pow(b1-b2,2);}boolcmp(stu a,stu b){returna.dis1b.dis1;}intmain(){ll a1,b1,a2,b2,n;cina1b1a2b2n;for(ll i1;in;i){cind[i].xd[i].y;d[i].dis1dist(d[i].x,d[i].y,a1,b1);d[i].dis2dist(d[i].x,d[i].y,a2,b2);}sort(d1,d1n,cmp);ll ansd[n].dis1;ll cnt0;for(ll in;i1;i--){ansmin(ans,cntd[i].dis1);cntmax(cnt,d[i].dis2);}ansmin(ans,cnt);coutansendl;return0;}