Adament Cabin

  • 计算机
    • Algorithm
    • Linux
    • Problems
    • NEUQACM
  • 日语学习
  • ACG
    • 追番列表
    • 游戏
  • 常日说
  • 杂物
    • 资料
    • 资源
    • 治疗中心
  • ao的链接
  • 分站
  • Chinese
    • Japanese
Adament Cabin
恋厨综合症第二治疗中心
  1. 首页
  2. 计算机
  3. Problems
  4. 正文

POJ-1328 Radar Installation

2022年7月23日 479点热度 0人点赞 0条评论

1328 -- Rader Installation

Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the coasting, can only cover d distance, so an island in the sea can be covered by a radius installation, if the distance between them is at most d.

We use Cartesian coordinate system, defining the coasting is the x-axis. The sea side is above x-axis, and the land side below. Given the position of each island in the sea, and given the distance of the coverage of the radar installation, your task is to write a program to find the minimal number of radar installations to cover all the islands. Note that the position of an island is represented by its x-y coordinates.

Figure A Sample Input of Radar Installations

Input

The input consists of several test cases. The first line of each case contains two integers n (1<=n<=1000) and d, where n is the number of islands in the sea and d is the distance of coverage of the radar installation. This is followed by n lines each containing two integers representing the coordinate of the position of each island. Then a blank line follows to separate the cases.

The input is terminated by a line containing pair of zeros

Output

For each test case output one line consisting of the test case number followed by the minimal number of radar installations needed. "-1" installation means no solution for that case.

Sample Input

3 2
1 2
-3 1
2 1

1 2
0 2

0 0

Sample Output

Case 1: 2
Case 2: 1

将各个点“投影”到x轴上,这里的投影指的是在X轴上标记出能扫描到这个点的雷达的可选位置。实现来说就是这个区间上的雷达都能扫描到改点。于是这个题转换为了要多少点落在区间上可以符合题目情境。

接下来,从左到右,如果一个区间的左边嵌入到了上一个区间的话,这两个区间只需要一个雷达即可满足。多个同理。所以我们从左遍历到右(这个区间左右的排列是区间的右端点的左右排列的)如果下一个区间的左边小于这个区间的右边,就可以忽视下一个区间不计算。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
struct interval{
    double start;
    double end;
    bool being_occupied;
};
vector<interval> inter;
bool cmp(interval a,interval b){
    return a.end<b.end;
}
int main(){
 //   freopen("TrueExample.txt","r",stdin);
  //  freopen("Out.txt","w",stdout);
    for(int example=1;;example++){
        inter.clear();
        int n,d;
        cin >> n >> d;
        if(n==0&&d==0) return 0;
        bool can_t=false;
        if(d<0) can_t=false;
        for(int i=0;i<n;i++){
            int px,py;
            cin >> px >> py;
            if(py>d) can_t=true;
            interval I;
            I.being_occupied=false;
            I.start=(double)px-sqrt(d*d-py*py);
            I.end=(double)px+sqrt(d*d-py*py);
            inter.push_back(I);
        }
        if(can_t){
            cout << "Case " << example << ": -1" << endl;
            continue;
        }
        sort(inter.begin(),inter.end(),cmp);
        int points=0;
        for(int i=0;i<inter.size();i++){
            if(inter[i].being_occupied) continue;
            inter[i].being_occupied=true;
            for(int j=i+1;j<inter.size();j++){
                if(inter[j].start<=inter[i].end){
                    inter[j].being_occupied=true;
                }
                if(inter[j].start>inter[i].end) break;
            }
            points++;
        }
        cout << "Case " << example << ": " << points << endl;
    }
}

来个劲爆的样例:

2 5
-3 4
-6 3


4 5
-5 3
-3 5
2 3
3 3

20 8
-20 7
-18 6
-5 8
-21 8
-15 7
-17 5
-1 5
-2 3
-9 6
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 7
9 6
10 5
0 0

2 3
0 2
2 3

2 3
0 2
1 3

3 3
1 2
-3 2
2 4

8 5
2 4
-4 4
-3 3
-3 1
-3 0
-1 0
0 5
6 0

3 0
1 2
-3 1
2 1

3 2
1 2
-3 1
2 1

1 2
0 2


2 3
0 2
2 3

4 -5
4 3
4 3
2 3
6 -9



3 -3
1 2
-3 2
2 1

6 2
1 2
1 2
1 2
-3 1
2 1
0 0

1 2
0 2

2 3
0 2
1 3

3 10
1 10
2 3
4 5

3 5
1 10
2 3
4 5

4 7
1 10
2 3
4 5
0 0

3 9
1 10
2 3
4 5
0 0

来个劲爆的输出:

case 1: 1
case 2: 2
case 3: 4
case 4: 1
case 5: 1
case 6: -1
case 7: 3
case 8: -1
case 9: 2
case 10: 1
case 11: 1
case 12: -1
case 13: -1
case 14: 2
case 15: 1
case 16: 1
case 17: 1
case 18: -1
case 19: -1
case 20: -1
标签: C/C++/C#
最后更新:2022年8月11日

BiyiAdopac

是铁龙鸣。

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

分类
  • Algorithm / 5篇
  • Linux / 5篇
  • NEUQACM / 9篇
  • Problems / 3篇
  • 常日说 / 2篇
  • 日本語 / 2篇
  • 游戏 / 1篇
  • 计算机 / 22篇
  • 资料 / 4篇
标签聚合
Physics ArchLinux LaTex Learning C/C++/C# Magisk Arcaea
ヤツメ穴
https://www.adament.xyz/wp-content/uploads/2022/03/ヤツメ穴(BGM).mp3
クリスタルグラビティ
https://www.adament.xyz/wp-content/uploads/2022/08/CrystalGravity.mp3

COPYRIGHT © 2022 adament.xyz. ALL RIGHTS RESERVED.
本站虽然不重要但是还是有的 隐私政策