P1158

题意

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

思路

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

代码

#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;
}