Fork me on GitHub

poj 1328 Radar Installation

发表于 | 分类于

原题

题目大意：

x轴上方有n个小岛，现在x轴上建造雷达，每个雷达的辐射范围是d为半径的圆。求：为使所有小岛被辐射到，应当建造几个雷达。

题解：

情况：

1、要使小岛被辐射到，则小岛距离雷达距离小于等于雷达半径，

但通过雷达位置判断与小岛距离是难以实现的。

解决：

1、依次记录每个小岛可以被辐射到的雷达位置的范围并排序，若范围有交集则可以共同使用一雷达，若无交集则新建雷达。eg. 岛B左边界小于等于岛A右边界，则当前不需新建雷达，岛C左边界小于等于岛B但大于岛A边界，则当前应当新建一个雷达。

注意：岛与雷达距离计算公式：sqrt( (double) d d - y y);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long
int n,d;
struct emm
{
    double r,l;
} isl[1001];//记录各岛可以被辐射的左右边界
bool cmp(emm a,emm b)
{
    return a.l<b.l;
}
int main()
{
    int cc=1;
    ios::sync_with_stdio(false);
    while(cin>>n>>d)
    {
        if(n==0&&d==0)break;
        int ans=1;//记录雷达个数,起始为一个雷达
        bool f=false;
        int x,y;
        for(int i=0; i<n; i++)
        {
            scanf("%d%d", &x, &y);
            if(y>d)f=true;//岛到x轴垂直距离比d大时无解
            else//记录左右路径，注意double
            {
                double len=sqrt((double)d*d-y*y);
                isl[i].r=(double)x+len;
                isl[i].l=(double)x-len;
            }
        }
        if(f)
        {
            cout<<"Case "<<cc++<<": -1"<<endl;
            continue;
        }
        sort(isl, isl+n,cmp);//对左边界排序
        double now=isl[0].r;//当前雷达辐射范围右边界
        for(int i=1; i<n; i++)//判断是否在辐射范围之内
        {
            if(isl[i].r<now)now=isl[i].r;
            else if(now<isl[i].l)
            {
                now=isl[i].r;
                ans++;
            }
        }
        cout<<"Case "<<cc++<<": "<<ans<<endl;
    }
    return 0;
}