题解：P1158 [NOIP2010 普及组] 导弹拦截

Heart_of_Iron · 2025-01-08 08:36:11 · 题解

思路

贪心！用公式 (x1-x)^2+(y1-y)^2 把它放进结构体 d[i].d1 ，(x2-x)^2+(y2-y)^2 把它放进结构体 d[i].d2。然后 sort 一下让 r_1{^2}+r_2{^2} 最小，然后定义一个结构体数组存 r_1 和 r_2，然后从大到小排序，最后 ans=min(d[i+1].d1+r2,ans); 一下就行了（ans 的值需要很大）。

警示后人

用了万能头不能用 x1,x2,y1,y2 之类的变量。所以我才用 define。

代码

#include<bits/stdc++.h>
#define x1 X1
#define x2 X2
#define y1 Y1
#define y2 Y2
#define int long long
using namespace std;
int x1,x2,y1,y2,r1,r2,ans=0x3ffffffff,n;
struct node
{
    int d1,d2;
}d[114514];
bool cmp(node x,node y)
{
    return x.d1>y.d1;
}
signed main() 
{
    cin >> x1 >> y1 >> x2 >> y2 >> n;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin >> x >> y;
        d[i].d1=(x1-x)*(x1-x)+(y1-y)*(y1-y);
        d[i].d2=(x2-x)*(x2-x)+(y2-y)*(y2-y);
    }
    sort(d+1,d+n+1,cmp);
    ans=d[1].d1;
    for(int i=1;i<=n;i++)
    {
        r2=max(r2,d[i].d2);
        ans=min(d[i+1].d1+r2,ans);
    }
    cout << ans;
    return 0;
}