#29384: C++ AC


shangpai (shangpai)

學校 : 不指定學校
編號 : 181267
來源 : [1.200.71.150]
最後登入時間 :
2022-03-25 20:19:12
a480. 導彈攔截系統 -- 100學年度彰雲嘉區資訊學科能力競賽 | From: [1.200.19.8] | 發表日期 : 2022-02-22 18:46

#include <bits/stdc++.h>

using namespace std;

#define ll long long

 

//兩個基地座標:

struct base {

ll x, y;

};

//城市座標、和與兩個基地的距離:

struct city {

ll x, y, dis_a, dis_b;

};

//計算基地與城市的距離:

int dis(base a, city b) {

return pow((a.x - b.x), 2) + pow((a.y - b.y), 2);

}

 

bool cmp(city a, city b) {

   return a.dis_a < b.dis_a;

}

 

 

city c[1000000] = {0};

 

int main(){

    ios::sync_with_stdio(0), cin.tie(0);

    

int n;

base a, b;

 

cin >> a.x >> a.y >> b.x >> b.y >> n;

for (int i = 0; i < n; i++) {

cin >> c[i].x >> c[i].y;

//計算距離

c[i].dis_a = dis(a, c[i]);

c[i].dis_b = dis(b, c[i]);

}

//將城市與第一個基地的距離由小排到大:

sort(c, c + n, cmp);

//將城市與第二個基地的距離都設定為「從這個城市開始,所有城市與第二個基地的最大距離」(好像繞口令XD):

    for (int i = n - 2; i >= 0; i--) {

        c[i].dis_b = max(c[i].dis_b, c[i + 1].dis_b);

    }

//判斷哪種組合能量消耗最少:

ll ans = LONG_LONG_MAX;

for (int i = 0; i < n; i++) {

ll distance = c[i].dis_a;

ll dis2 = 0;

if (i < n - 1) { //如果第二個基地有啟動防護半徑:

   dis2 = c[i + 1].dis_b;

}

distance += dis2;

ans = min(distance, ans);

}

//有可能第一個基地也沒有啟動防護半徑:

ans = min(c[0].dis_b, ans);

 

cout << ans << "\n";

 

}

 
ZeroJudge Forum