2010J__3：导弹拦截

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

/**************************************************************** 
 * Description: 2009年普及组第三题  导弹拦截
 * Author: Alex Li
 * Date: 2024-10-19 04:46:01
 * LastEditTime: 2024-10-19 04:53:57
****************************************************************/
#include <bits/stdc++.h>
using namespace std;

// 计算两点之间的平方距离，采用内联函数以提高效率
inline int dist(int x1, int y1, int x2, int y2) {
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}

// 定义结构体 Jack，存储导弹到两套系统的距离平方
struct Jack {
    int l1, l2;  // l1 是导弹到第一套系统的距离平方，l2 是到第二套系统的距离平方
} f[110000];

// 自定义比较函数，按 l1 排序，l1 较小的排在前面
inline bool cmp(const Jack &a, const Jack &b) {
    return a.l1 < b.l1;
}

int main() {
    std::ios::sync_with_stdio(false);  // 关闭同步以加快 cin/cout 速度
    int n, x1, y1, x2, y2;  // n 为导弹数量，(x1, y1) 和 (x2, y2) 是两套系统的坐标
    cin >> x1 >> y1 >> x2 >> y2;  // 输入两套拦截系统的坐标
    cin >> n;  // 输入导弹数量

    // 读取每个导弹的坐标，并计算它与两套系统的距离平方
    for (int i = 1; i <= n; i++) {
        int a, b;  // 导弹的坐标
        cin >> a >> b;
        f[i].l1 = dist(x1, y1, a, b);  // 计算与第一套系统的距离平方
        f[i].l2 = dist(x2, y2, a, b);  // 计算与第二套系统的距离平方
    }

    // 按照导弹到第一套系统的距离平方进行升序排序
    sort(f + 1, f + n + 1, cmp);

    // 初始化答案为最远导弹到第一套系统的距离平方
    int ans = f[n].l1;
    int maxL2 = -1;  // 记录第二套系统能拦截的最大距离平方

    // 倒序遍历导弹列表，逐步计算最优方案
    for (int i = n - 1; i >= 1; i--) {
        maxL2 = max(maxL2, f[i + 1].l2);  // 更新第二套系统拦截的最大距离平方
        ans = min(ans, maxL2 + f[i].l1);  // 计算当前最小代价
    }

    cout << ans << endl;  // 输出当天的最小使用代价
    return 0;
}