P1325 雷达安装

题目描述

描述：

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

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

样例1如图所示

输入输出格式

输入格式：

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

接下来n行为岛屿坐标。

输出格式：

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

输入输出样例

输入样例#1：复制

输出样例#1：复制

说明

数据范围

$x_i | le 2 imes 10^6∣xi∣≤2×106 ,0 le y_i le 200000≤yi≤20000$

//* 雷达覆盖问题 - 问题转化：
//-1、将问题稍微进行转化：将基站设为覆盖半径为 D。 则问题变为：每个基站的覆盖区域必须要有雷达。
//-2、又因为雷达只能放在 X 轴上，所以每个基站覆盖的其实是一条线段。 则问题变为：每条线段上必须要要 有雷达。
//-3、又因为雷达只能放在 X 轴上，所以每个基站覆盖的其实是一条线段。则问题变为：每条线段上必须要要 有雷达。
//
//问题：如何贪心？回想活动安排问题。
//解题思路：
//先计算出每个岛屿与x轴的左右交点，然后按照右端点进行排序，枚举每一个岛屿，
//①如果这个岛屿没有被雷达覆盖，那么就将一个雷达放在其与x轴的右端交点，并枚举这个岛屿后面的岛屿，判断这个雷达能否将后面的岛屿覆盖。 
//②如果该岛屿已经被覆盖，则直接跳过。


#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define date 100005
using namespace std;
int n;
int d;
int sum;
int x,y;
float z;
int line[date];
struct Point
{
    float x;
    float y;
    bool flag;
}point[date];
bool cmp(Point a,Point b)        //按照与x轴右侧的交点排序 
{
    return a.y<b.y;
}
void work()
{
    for(int i=1;i<=n;i++)
    {
        if(!point[i].flag)        //如果此处没有被雷达覆盖 
        {
            point[i].flag=1;    //把雷达放在与x轴右侧的交点 
            sum++;                //雷达数加一 
            for(int j=i+1;j<=n;j++)        //枚举后面的岛屿 
            {
                if(!point[j].flag&&point[j].x<=point[i].y)        //如果后面的岛屿没有被雷达覆盖，并且与当前的岛有交点 
                {
                    point[j].flag=1;            //标记为已被覆盖 
                }
            }
        }
    }
    cout<<sum;
}
void init()
{
    scanf("%d",&n);
    scanf("%d",&d);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        if(y>d)
        {
            cout<<-1;
            return;
        }
        z=sqrt(d*d-y*y);        //计算与x轴的交点 
        point[i].x=x-z;            //左交点 
        point[i].y=x+z;            //右交点 
    }
    sort(point+1,point+n+1,cmp);    //排序 
    work();
}
int main()
{
    init();
    return 0;
}