a480: 導彈攔截系統

題目連結: https://zerojudge.tw/ShowProblem?problemid=a480

# 內容

某個國家研發了一套導彈攔截系統，只要設定了防護半徑 r，在距離系統設置處 r 以內的範圍都會受到防護。此外，他們發現，啟用該系統會消耗大量的能源，且能源消耗為 r2。

在研發完成之際，敵國隨即向他們發射飛彈展開攻擊。不幸的是，該系統仍在試驗階段，所以目前僅設置於兩處 (x1, y1) 與 (x2, y2)。由於能源消耗過於龐大，要使防護持久就必須讓能源消耗越小越好。因此，他們希望能以最少的能源消耗下防護境內所有的 n 個城市。

為了簡單起見，城市位置以一點 (xi, yi) 來表示。

# 解題思路

設城市與導彈攔截系統 1,2 的距離為 d1,d2
先對各城市 d1 排序，之後再窮舉求 p
p = c[i].d1 + max(c[i+k].d2),k>=1
(i 城市與導彈 1 的距離) (其它城市與導彈 2 的最大距離)

# 程式碼

#include <bits/stdc++.h>
using namespace std;

struct box{
    int d1,d2;
};

bool comp( box a, box b ){
    return(a.d1<b.d1);
}

int main(){std::ios::sync_with_stdio(false); std::cin.tie(0);
    int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    int n;
    cin>>n;

    box dis[n];
    int tx,ty;
    for(int i=0;i<n;i++){
        cin>>tx>>ty;
        dis[i].d1=(x1-tx)*(x1-tx)+(y1-ty)*(y1-ty);
        dis[i].d2=(x2-tx)*(x2-tx)+(y2-ty)*(y2-ty);
    }
    sort(dis,dis+n,comp);
    for(int i=n-2;i>=0;i--)
        dis[i].d2=max(dis[i].d2,dis[i+1].d2);
    int ans=2147483647;
    for(int i=0;i<n;i++){
        int p=dis[i].d1;
        int temp=0;
        if(i!=n-1) temp=dis[i+1].d2;
        p += temp;
        ans=min(ans,p);
    }
    ans = min(ans , dis[0].d2);
    cout<<ans;
}