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