题解 P1158 【导弹拦截】

OptimusPrime_L · 2017-07-03 23:45:30 · 题解

这题不难，思路是：

先把每一个导弹对应的两个系统的距离平方值存储在结构数组sum的s1和s2里，然后按照其中一个的值进行排序，从已排序的序列最大值开始扫。初始情况是所有导弹归s1管（请看注意）。把扫过的导弹归s2管，然后求出作战半径平方和，因为不用输出最小值的具体哪个导弹归哪个系统管，直接擂台法比出最小值即可。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxN = 100000+5;
struct node
{
    int x,y;
}s1,s2,m[maxN];
struct struct_node
{
    int s1,s2;
}sum[maxN];
int n;
int comp(struct_node a,struct_node b)
{
    return a.s1<=b.s1;
}
int main()
{
    cin >> s1.x >> s1.y >> s2.x >> s2.y;
    cin >> n;
    for (int i=1;i<=n;i++)
    {
        cin >> m[i].x >> m[i].y;
    }
    for (int i=1;i<=n;i++)
    {
        sum[i].s1=abs(m[i].x-s1.x)*abs(m[i].x-s1.x)+abs(m[i].y-s1.y)*abs(m[i].y-s1.y);
        sum[i].s2=abs(m[i].x-s2.x)*abs(m[i].x-s2.x)+abs(m[i].y-s2.y)*abs(m[i].y-s2.y);
    }
    sort(sum+1,sum+n+1,comp);
    int min=sum[n].s1,max=-1;
    for (int i=n;i>=1;i--)
    {
        if (sum[i].s2>max)
        {
            max=sum[i].s2;
        }
        if (sum[i-1].s1+max<min)
        {
            min=sum[i-1].s1+max;
        }
    }
    cout << min << endl;
    system("pause");
    return 0;
}

注意：

一开始过了8个，第一个数据就错，下载下来一看，原因是代码中变量min的初值应该是全部归s1管的情况，而不是设为0x7fffffff

改完就过了。