这样行不通啊,没法保证是最优解
![](https://cdn.luogu.com.cn/upload/image_hosting/c44h2cpl.png)
比如这样
用2拦截更近
![](https://cdn.luogu.com.cn/upload/image_hosting/bygixzej.png)
但如果在B点又有一个,用1拦截,这时刚才的导弹也在1的范围内,不需要2了
排序和枚举肯定是要的
```cpp
//新鲜的代码
#include<bits/stdc++.h>
using namespace std;
struct z{
int a,b;
int d1,d2;
}x[100010];
int x1,x2,y3,y2,n,j,k;
int t[100010];
bool cmp(z z1,z z2){
return z1.d1<z2.d1;
}
int main(){
cin>>x1>>y3>>x2>>y2>>n;
for(int i=1;i<=n;i++){
cin>>x[i].a>>x[i].b;
x[i].d1=(x[i].a-x1)*(x[i].a-x1)+(x[i].b-y3)*(x[i].b-y3);
x[i].d2=(x[i].a-x2)*(x[i].a-x2)+(x[i].b-y2)*(x[i].b-y2);
}
sort(x+1,x+n+1,cmp);//按到1的距离排序
for(int i=n;i>=1;i--){
t[i]=max(t[i+1],x[i].d2);
}//计算i后面的导弹到2的最大距离
int ans=INT_MAX;
for(int i=1;i<=n;i++){
ans=min(ans,x[i].d1+t[i+1]);
}
cout<<ans;
return 0;
}
```
具体思路可以看看题解
by ylm0x7D9 @ 2024-04-24 09:13:33
@[ylm0x7D9](/user/625707) 已关,感谢
by 2012_Zhang_ @ 2024-04-24 17:33:38