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
输入 #1
0 0 10 0 2 -3 3 10 0输出 #1
18输入输出样例 #2
输入 #2
0 0 6 0 5 -4 -2 -2 3 4 0 6 -2 9 1输出 #2
30说明/提示
两个点( 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^2+r_2^2r12+r22。
样例 1 说明
样例1 11中要拦截所有导弹，在满足最小使用代价的前提下，两套系统工作半径的平方分别为18 1818和0 00。
样例 2 说明
样例2 22中的导弹拦截系统和导弹所在的位置如下图所示。要拦截所有导弹，在满足最小使用代价的前提下，两套系统工作半径的平方分别为20 2020和10 1010。
【数据范围】。
- 对于10 % 10\%10%的数据，N = 1 N=1N=1。
- 对于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最大半径、枚举最优解。
效率保障：排序+线性遍历，无浮点运算，高效处理十万级数据量。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=2e5+10;constll p=1e9+7;constll INF=1e18;constll M=1e6+10;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.dis1<b.dis1;}intmain(){ll a1,b1,a2,b2,n;cin>>a1>>b1>>a2>>b2>>n;for(ll i=1;i<=n;i++){cin>>d[i].x>>d[i].y;d[i].dis1=dist(d[i].x,d[i].y,a1,b1);d[i].dis2=dist(d[i].x,d[i].y,a2,b2);}sort(d+1,d+1+n,cmp);ll ans=d[n].dis1;ll cnt=0;for(ll i=n;i>=1;i--){ans=min(ans,cnt+d[i].dis1);cnt=max(cnt,d[i].dis2);}ans=min(ans,cnt);cout<<ans<<endl;return0;}
