18.导弹拦截

18.[NOIP2010 普及组] 导弹拦截
难度：普及-
来源：--

AC代码（C++/C#）：

#include <iostream>
#include <algorithm> // The library that sort must call
using namespace std;
int x1,y1,x2,y2,n; // The five numbers entered are generated into global variables for the convenience of the cmp function
int d[100007]; // d array is preprocessed. See the idea for specific use
struct node
{
    int x; // Record the position information of the missile
    int y;
}w[100007];
bool cmp(node a,node b)
{
    int q = (x1 - a.x) * (x1 - a.x) + (y1 - a.y) * (y1 - a.y);
    int p = (x1 - b.x) * (x1 - b.x) + (y1 - b.y) * (y1 - b.y);
    return q < p;
}
int main(void)
{
    int ans = 0;
    cin >> x1 >> y1 >> x2 >> y2;
    cin >> n;
    for (int i = 0;i < n;i++)
    {
        cin >> w[i].x >> w[i].y;
    }
    sort(w,w + n,cmp);
    for (int i = n - 1;i >= 0;i--)
    {
        int h = (x2 - w[i].x) * (x2 - w[i].x) + (y2 - w[i].y) * (y2 - w[i].y); // Pretreatment process
        d[i] = max(d[i + 1],h);
    }
    ans = d[0];
    for (int i = 0;i < n;i++)
    {
        int cnt = 0;
        cnt = (x1 - w[i].x) * (x1 - w[i].x) + (y1 - w[i].y) * (y1 - w[i].y);
        cnt += d[i + 1]; // Since the maximum value reserved by d [i] includes i, i belongs to the prefix
        ans = min(ans,cnt); 
    }
    ans = min(ans,d[0]);
    cout << ans;
    return 0;
}

• 没有注释，自行学习。
• by：ጿ ኈ ቼ ዽ ጿ

---

你的点赞和关注就是我更新题解的最大动力！

---

——————————点个赞吧 ↓ ！——————————