题解 P1158 【导弹拦截】

a2956331800 · 2017-02-05 14:50:32 · 题解

有技巧的枚举

先算出每个点到两个拦截系统的距离的平方（不要开方，因为最后要的就是平方和），用一个结构体记录，分别为f1、f2，按f1从小到大排序

struct node
{
    int f1,f2;
    bool operator <(const node&a)const
    {
        return f1<a.f1;
    }
};

排序完之后，用另一个数组mx，第i个记录第i个到第n个f2中最大的一个f2： for(i=n;i>=1;i--)

mx[i]=max(mx[i+1],point[i].f2);

然后从1到n枚举，求出第一套系统打前i个（第i个f1），第二套打第i+1个到第n个时的代价（mx[i+1]），取最小值

now=point[i].f1+mx[k];

if(now<best)

best=now;

每次计算的复杂度为O（1）

快排复杂度为O（nlogn）,总复杂度为O(nlogn)

完整代码：

#include<algorithm>
#include<iostream>
using namespace std;
struct node
{
    int f1,f2;
    bool operator <(const node&a)const
    {
        return f1<a.f1;
    }
};
node point[100001];
int x1,y1,x2,y2,n,x,y,i,k,now,best=0x7fffffff,mx[100002];
int far(int x1,int y1,int x2,int y2)
{
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
int main()
{
    cin>>x1>>y1>>x2>>y2>>n;
    for(i=1;i<=n;i++)
    {
        cin>>x>>y;
        point[i].f1=far(x,y,x1,y1);
        point[i].f2=far(x,y,x2,y2);
    }
    sort(point+1,point+1+n);
    for(i=n;i>=1;i--)
      mx[i]=max(mx[i+1],point[i].f2);
    for(i=1;i<=n;i++)
    {
        k=i+1;
        while(point[k].f1==point[i].f1&&k<=n)
          k++;
        now=point[i].f1+mx[k];
        if(now<best)
          best=now;
    }
    cout<<best;
    return 0;
}