題目連結:https://zerojudge.tw/ShowProblem?problemid=a480
想法
先將所有城市按照與基地1的距離從近到遠排序,再來一一枚舉基地1的半徑,不在基地1範圍內的,就是基地2的(半徑要取最大值)。
實作細節
suf[i] 代表 suf[i].d2、suf[i+1].d2、suf[i+2].d2、…、suf[n-1].d2 之中的最大值。
for(int i=n-1; i>=0; i--){
suf[i] = max(suf[i+1], c[i].d2);
}
程式碼
#include <bits/stdc++.h>
using namespace std;
struct City{
int d1, d2;
};
bool cmp(City a, City b){
return a.d1 < b.d1;
}
const int N = 1000005;
int suf[N];
int main(){
ios::sync_with_stdio(0), cin.tie(0);
int x1, y1, x2, y2, n, x, y, ans=INT_MAX, r1, r2;
cin >> x1 >> y1 >> x2 >> y2 >> n;
City c[n];
for(int i=0; i<n; i++){
cin >> x >> y;
c[i].d1 = pow(x-x1,2)+pow(y-y1,2);
c[i].d2 = pow(x-x2,2)+pow(y-y2,2);
}
sort(c, c+n, cmp);
for(int i=n-1; i>=0; i--){
suf[i] = max(suf[i+1], c[i].d2);
}
for(int i=-1; i<n; i++){
if(i == -1) r1 = 0;
else r1 = c[i].d1;
r2 = suf[i+1];
ans = min(ans, r1+r2);
}
cout << ans << '\n';
}