【题解】导弹拦截

佚名 6年前 (2019-05-11) 随笔 1032人围观抢沙发百度已收录

题目描述

经过11年的韬光养晦，某国研发出了一种新的导弹拦截系统，凡是与它的距离不超过其工作半径的导弹都能够被它成功拦截。当工作半径为0时，则能够拦截与它位置恰好相同的导弹。但该导弹拦截系统也存在这样的缺陷：每套系统每天只能设定一次工作半径。而当天的使用代价，就是所有系统工作半径的平方和。

某天，雷达捕捉到敌国的导弹来袭。由于该系统尚处于试验阶段，所以只有两套系统投入工作。如果现在的要求是拦截所有的导弹，请计算这一天的最小使用代价。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

输入格式

第一行包含4个整数x1、y1、x2、y2，每两个整数之间用一个空格隔开，表示这两套导弹拦截系统的坐标分别为（x1，y1）、（x2，y2）。

第二行包含1个整数N，表示有N颗导弹。接下来N行，每行两个整数x、y，中间用一个空格隔开，表示一颗导弹的坐标（x，y）。不同导弹的坐标可能相同。

输出格式

一行，包含一个整数，即当天的最小使用代价。

输入样例一

0 0 10 0

-3 3

10 0

输出样例一

输入样例二

0 0 6 0

-4 -2

-2 3

4 0

6 -2

9 1

输出样例二

样例说明

样例一说明：样例一中要拦截所有导弹，在满足最小使用代价的前提下，两套系统工作半径的平方分别为18和0。

样例二说明：样例二中的导弹拦截系统和导弹所在的位置如下图所示，要拦截所有导弹，在满足最小使用代价的前提下，两套系统工作半径的平方分别为20和10。

数据规模

对于10%的数据，N=1；

对于20%的数据，1≤N≤2；

对于40%的数据，1≤N≤100；

对于70%的数据，1≤N≤1000；

对于100%的数据，1≤N≤100000，且所有坐标分量的绝对值都不超过1000。

题解

我们对导弹按照距离系统一的距离排序，然后枚举第$1$到第$i$个导弹由系统一拦截，第$(i+1)$到第$n$个导弹由系统二拦截，其中的最优解即可。

#include <iostream>
#include <algorithm>
#include <cstdio>

#define MAX_N 100000
#define Max(x, y) (x >= y ? x : y)
#define Min(x, y) (x <= y ? x : y)

using namespace std;

int x1, y1, x2, y2;
int n;
struct Node
{
    int x, y;
    int dis1, dis2;
}a[MAX_N | 1];
int ans;

inline bool Compare(Node x, Node y)
{
    return x.dis1 < y.dis1;
}

int main()
{
    scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &n);
    for(register int i = 1; i <= n; ++i)
    {
        scanf("%d%d", &a[i].x, &a[i].y);
        a[i].dis1 = (a[i].x - x1) * (a[i].x - x1) + (a[i].y - y1) * (a[i].y - y1);
        a[i].dis2 = (a[i].x - x2) * (a[i].x - x2) + (a[i].y - y2) * (a[i].y - y2);
    }
    sort(a + 1, a + n + 1, Compare);
    int tmp = 0;
    ans = a[n].dis1;
    for(register int i = n - 1; i >= 0; --i)
    {
        tmp = Max(tmp, a[i + 1].dis2);
        ans = Min(ans, a[i].dis1 + tmp);
    }
    printf("%d", ans);
    return 0;
}