【題解】a480: 導彈攔截系統

題目連結：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';
}