洛谷 P1325 雷达安装 题解【贪心】【解析几何】

作者: wjyyy 分类: 数学,解析几何,解题报告,贪心 发布时间: 2018-07-12 15:42

点击量:24

 

   贪心再次毒瘤

 

题目描述

假设海岸线是一条无限延伸的直线。它的一侧是陆地,另一侧是海洋。每一座小岛是在海面上的一个点。雷达必须安装在陆地上(包括海岸线),并且每个雷达都有相同的扫描范围d。你的任务是建立尽量少的雷达站,使所有小岛都在扫描范围之内。

 

数据使用笛卡尔坐标系,定义海岸线为x轴。在x轴上方为海洋,下方为陆地。

 

样例1如图所示

输入输出格式

输入格式:

第一行包括2个整数n和d,n是岛屿数目,d是雷达扫描范围。

 

接下来n行为岛屿坐标。

 

输出格式:

一个整数表示最少需要的雷达数目,若不可能覆盖所有岛屿,输出“-1”。

 

输入输出样例

输入样例#1:
3 2
1 2
-3 1
2 1
输出样例#1:
2

说明

数据范围

\(n \le 1000,d \le 20000\)

\(| x_i | \le 2 \times 10^6, 0 \le y_i \le 20000\)

 

题解:

   一个比较坑的点是输出-1没有分因为我忘记输出-1还A了

 

   因为放在海岸线上一定比不放在海岸线上覆盖得要广,所以我们考虑只放在海岸线上【贪心】。这样如果要照顾一个点\((x,y)\),最好的放法是把雷达放在\((x\pm \sqrt{d^2-y^2},0)\)的位置,就刚好能照顾到这个点,但是可能会出现该点在圆内而雷达有机会照顾到别的点。但我们再想一下,别的点在最优的情况下,一定也处于这个雷达的圆上,以给别的点留下更多的空间。

 

   接着我们试着看一下有哪些雷达是必须放的,有哪些是可以不放的。我们如果统一把上面的雷达位置公式的\(\pm \)号换成+号,对答案其实是没有影响的,因为最右边的点如果不被左边点依附的雷达照顾到,就需要新开一个雷达了。尽管选定了雷达的右下角距离为d处,但是也不能直接就把岛屿所在的点从左到右排序,这样是有问题的:

   在这个图中,\(d=2,C(-4,1),B(-3,2),D(-2,1)\),我们如果把点按横坐标排序处理,就会出现这种状况。而在这个图中,如果把雷达设在\((-3,0)\)处,就可以把\(B,C,D\)三个点全部保护。通过这一点就可以看出,把右下角的极限点从左到右排序,从左到右扫描,如果当前雷达的对应岛屿(左上角距离为d处)没有被保护,这个点就要安放雷达;因为既然它到极限情况都照顾不了,更别提右边的点了。而检验自己对应的岛屿有没有被保护,只需要检查朝左数第一个安放的雷达有没有保护它。如果没有,那更左边的也不可能保护它。这样我们就在\(O(n\log n)\)的时间内完成了排序,在\(O(n)\)的时间完成了检验。

 

Code:

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::sort;
struct pnt
{
    double x,y;
    int n;
    friend bool operator <(pnt a,pnt b)
    {
        return a.x<b.x;
    }
}p[1010],t[1010];
bool used[1010];
int main()
{
    memset(used,0,sizeof(used));
    int n,d;
    scanf("%d%d",&n,&d);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&p[i].x,&p[i].y);
        t[i].n=i;
        t[i].x=p[i].x+sqrt(d*d-p[i].y*p[i].y);
        t[i].y=0.0;
    }
    sort(t+1,t+1+n);
    t[0].x=-3000000.0;
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        int j;
        for(j=i-1;j>=1;j--)
            if(used[j])
                break;
        if(used[j]&&(t[j].x-p[t[i].n].x)*(t[j].x-p[t[i].n].x)+(t[j].y-p[t[i].n].y)*(t[j].y-p[t[i].n].y)<=d*d)
            continue;
        used[i]=1;
        sum++;
    }
    printf("%d\n",sum);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */