题解：P1158 [NOIP2010 普及组] 导弹拦截

china_history · 2025-01-09 16:24:09 · 题解

题意

就是给你机器的工作半径，每次工作要花钱，就是工作半径的平方，问你怎么花最少的钱，拦截所有导弹。

思路

每次通过我们的公式计算距离，存入并排序，最后即可得出答案。

代码

#include <bits/stdc++.h>
using namespace std;
struct s {
    int w1, v1;
    bool operator < (const s &a){//重载
        return w1< a.w1;    
    }
};
int main() {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;//输入坐标
    int n;
    cin >> n;
    s a[100001];
    int f[100011];
    int cnt = 1<<30;//设置极大值
    for(int i=1;i<=n;i++){
        int x,y;
        cin >> x >> y;
        a[i].w1=(x-x1)*(x-x1)+(y-y1)*(y-y1);//计算距离
        a[i].v1=(x-x2)*(x-x2)+(y-y2)*(y-y2);
    }
    sort(a+1,a+n+1);
    f[n+1]=0;
    for(int i=n;i>=1;i--){
        f[i]=max(f[i+1],a[i].v1);
    }
    for(int i=0;i<=n;i++){
        cnt=min(cnt,a[i].w1+f[i+1]);
    }
    cout << cnt;
    return 0;
}