题解 P1158 【导弹拦截】

NewSjf · 2019-11-30 13:19:23 · 题解

大家好
由于我太菜并没有想出正确的贪心策略
所以我乱搞O(N)过了这道题
起初我想到了一个贪心策略
考虑到系统半径应该是由被拦截的最远的导弹决定的 所以考虑每个导弹分别放到系统1和系统2
取平方和最优的为俩系统工作半径
仔细一想似乎很有道理还没找到反例

#include<iostream>
#include<cstring>
#include<cmath>
#define MAXN 1000001
#define pi 3.1415926
using namespace std;
struct node
{
    double x,y;
    double friend operator-(const node a,const node b)
    {
        return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    }
}O1,O2,point;
double MaxDis1,MaxDis2;
int n;
int main()
{
//  freopen("testdata.in","r",stdin);
    cin>>O1.x>>O1.y>>O2.x>>O2.y;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>point.x>>point.y;
        if((O1-point)*(O1-point)+MaxDis2*MaxDis2<(O2-point)*(O2-point)+MaxDis1*MaxDis1) //选谁更优先
        {
            MaxDis1=max(MaxDis1,O1-point);
        }
        else MaxDis2=max(MaxDis2,O2-point);
    }
    cout<<MaxDis1*MaxDis1+MaxDis2*MaxDis2;
}

然后得到了60分的好成绩
蒟蒻想不出什么更好贪心策略,又不想翻题解
所以我将点的顺序随机打乱,重复跑15遍贪心取最优值
然后神奇的AC了这道题

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 1000001
#define pi 3.1415926
using namespace std;
struct node
{
    double x,y;
    double friend operator-(const node a,const node b)
    {
        return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    }
}O1,O2,point[MAXN];
double ans=2147483647.0;
int n;
int main()
{
//  freopen("testdata.in","r",stdin);
    ios::sync_with_stdio(false);
    cin>>O1.x>>O1.y>>O2.x>>O2.y;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>point[i].x>>point[i].y;
    }
    for(int t=1;t<=16;t++)  //随机打乱数组贪心50遍 
    {
        random_shuffle(point+1,point+1+n);
        double MaxDis1=0,MaxDis2=0;
        for(int i=1;i<=n;i++)
        {
            if((O1-point[i])*(O1-point[i])+MaxDis2*MaxDis2<(O2-point[i])*(O2-point[i])+MaxDis1*MaxDis1)
            {
                MaxDis1=max(MaxDis1,O1-point[i]);
            }
            else MaxDis2=max(MaxDis2,O2-point[i]);
        }
        if(MaxDis1<MaxDis2)
        {
            swap(MaxDis1,MaxDis2);
            swap(O1,O2);
        }
        if(O1-O2+MaxDis2<=MaxDis2)MaxDis2=0;
        ans=min(ans,MaxDis1*MaxDis1+MaxDis2*MaxDis2);
    }
    cout<<(int)ans<<endl;
}

轻微压行一下

#include<iostream>
#include<cmath>
#include<algorithm>
#define MAXN 1000001
using namespace std;
struct node
{
    double x,y;
    double friend operator-(const node a,const node b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
}O1,O2,point[MAXN];
double ans=2147483647.0;
int n;
int main()
{
    cin>>O1.x>>O1.y>>O2.x>>O2.y>>n;
    for(int i=1;i<=n;i++)cin>>point[i].x>>point[i].y;
    for(int t=1;t<=16;t++)  //随机打乱数组贪心50遍 
    {
        random_shuffle(point+1,point+1+n);
        double MaxDis1=0,MaxDis2=0;
        for(int i=1;i<=n;i++)
        {
            if((O1-point[i])*(O1-point[i])+MaxDis2*MaxDis2<(O2-point[i])*(O2-point[i])+MaxDis1*MaxDis1)
                MaxDis1=max(MaxDis1,O1-point[i]);
            else MaxDis2=max(MaxDis2,O2-point[i]);
        }
        if(MaxDis1<MaxDis2)swap(MaxDis1,MaxDis2),swap(O1,O2);
        if(O1-O2+MaxDis2<=MaxDis2)MaxDis2=0;
        ans=min(ans,MaxDis1*MaxDis1+MaxDis2*MaxDis2);
    }
    cout<<(int)ans<<endl;
}

32行代码,400ms跑完,自我感觉还听良好的
乱搞出奇迹