题解 P1158 【导弹拦截】

HFColin · 2017-11-02 21:58:32 · 题解

第一篇题解，请多指教不着浮点数，用勾股即可求出一个点到另一个的点的平方。我保险用了long long

假设第一个系统覆盖了x_1、x_2、x_3、x_4……x_p这些点，设其中与第一个系统距离平方和最大的点的距离平方和为l_1。

第二个系统覆盖了y_1、y_2、y_3、y_4……y_q这些点，设其中与第二个系统最大的点的距离平方和为l_2。

则系统的使用代价为l_1+l_2。

我们就把所有点距离第一套系统的平方排序，枚举！

枚举第一个系统的距离平方和最大的点的距离平方和，这样想必第一个系统可以覆盖所有距离平方和比它小的点。

再扫一遍所有的不被覆盖第一个系统的点，取与第二个系统最大的距离平方和。

这里就可得出结果。时间复杂度n*n

但是！！！

会超时

再处理其余的点的时候，第二个系统的点一个个加入，前面的最小值是固定的，因此，不用整个扫一遍，每次比较一次就可以了

下面是代码

#include<cstdio>
#include<algorithm>
using namespace std;
struct dis{
    long long l;//存所有点到第一个系统的平方和 
    int i;//存点的编号 
}p1[100000];//要从大到小排序 
bool const cmp(const dis &a,const dis &b)//从大到小排序 
{
    return a.l>b.l;
}
long long p2[100000];
int main()
{
//    freopen("missile.in","r",stdin);//文件输入输出 
//    freopen("missile.out","w",stdout);
    int x1,y1,x2,y2,n,x,y,i;
    long long xl,yl,Minn,ans,Maxn;
    scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
    scanf("%d",&n);
    for (i=0;i<n;i++)
    {
        scanf("%d %d",&x,&y);
        p1[i].i=i;
        xl=x-x1;
        yl=y-y1;
        p1[i].l=xl*xl+yl*yl;//这里不用取绝对值 ，因为是平方。 
        xl=x-x2;
        yl=y-y2;
        p2[i]=xl*xl+yl*yl;
    }
    // 
    sort(p1,p1+n,cmp);//枚举每一种情况 
    Minn=p1[0].l;
    Maxn=0;
    for (i=1;i<n;i++)
    {
        if (p2[p1[i-1].i]>Maxn) Maxn=p2[p1[i-1].i];
        ans=p1[i].l+Maxn;
        if (Minn>ans) Minn=ans;
    }
    //
    printf("%lld",Minn);
//    fclose(stdin); fclose(stdout);//文件输入输出 
    return 0;
}