POJ 1328 Radar Installation

Radar Installation

Time Limit:1000MS Memory Limit:10000KB 64bit IO Format:%I64d & %I64u

Appoint description:

Description

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

Sample Output

Case 1: 2
Case 2: 1

题意  ：有n个小岛 并给出海岸线上雷达覆盖的半径d，雷达只能放置于海岸线上（x轴），给出每个小岛的坐标，问至少要多少个雷达才能把小岛全部覆盖。

解法一：（左交点 从小到大排序）

思路：算出每个小岛能被覆盖的雷达的圆心范围，即以小岛为圆心 d为半径作圆，该圆与X轴的交点：

左交点为x-sqrt(d*d-y*y);

右交点为x+sqrt(d*d-y*y);

按照 左交点从小到大排序，第一个雷达放在第一个点的右交点，

如果某点的左交点在当前雷达的右边，则需安装一个新雷达，更新雷达的位置

否则如果某点的右交点也在当前雷达的左边，则把当前雷达的圆心更新为该点的右交点（因为：

有这种情况。）

 1 #include <iostream>
 2 #include <cmath>
 3 #include <algorithm>
 4 #include <cstdio>
 5 using namespace std;
 6 struct node
 7 {
 8     double left, right;
 9 }island[1001];
10 bool cmp(node a, node b)
11 {
12     return a.left < b.left;
13 }
14 int main()
15 {
16     double x, y, d, temp;
17     int i, cnt, n, k = 0;
18     bool flag;
19     while (scanf("%d%lf", &n, &d) && !(n == 0 && d == 0))
20     {
21         k++;
22         flag = false;
23         for (i = 0; i<n; i++)
24         {
25             scanf("%lf%lf", &x, &y);
26             if (y > d || d<0)
27             {
28                 flag = true;
29             }
30             island[i].right = x + sqrt(d*d - y * y);
31             island[i].left = x - sqrt(d*d - y * y);
32         }
33         if (flag)
34         {
35             printf("Case %d: -1
", k);
36             continue;
37         }
38         sort(island, island + n, cmp);
39         temp = island[0].right;
40         cnt = 1;
41         for (i = 1; i<n; i++)
42         {//分两种
43             if (island[i].right <= temp)
44             {
45                 temp = island[i].right;
46             }
47             else if (island[i].left > temp)
48             {
49                 cnt++;
50                 temp = island[i].right;
51             }
52         }
53         printf("Case %d: %d
", k, cnt);
54     }
55     return 0;
56 }

View Code

解法二：排序按右端点排，右小的在前，再左大的在前

则只需考虑 如果某点的左交点在当前雷达的右边，则需安装一个新雷达，更新雷达的位置

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<string> 
 4 #include<cstring>  
 5 #include<algorithm>  
 6 #include<cmath>  
 7 using namespace std;
 8 struct ac
 9 {
10     double l;
11     double r;
12 }p[1500];
13 
14 bool cmp(ac x, ac y)//排序按右端点排，右小的在前，再左大的在前
15 {
16     return (x.r != y.r) ? (x.r<y.r) : (x.l>y.l);
17 }
18 
19 int main()
20 {
21     int n, rad;
22     int d = 1;
23     while (~scanf("%d%d", &n, &rad), (n&&rad))
24     {
25         int x, y;
26         int f = 1;
27         for (int i = 0; i<n; i++)
28         {
29             scanf("%d%d", &x, &y);
30             if (rad >= y)//精彩的初始化，从二维问题变成一维问题
31             {
32                 p[i].l = x - sqrt((double)rad*rad - (double)y*y);
33                 p[i].r = x + sqrt((double)rad*rad - (double)y*y);
34             }
35             else
36             {
37                 f = 0;
38             }
39         }
40         if (!f)
41         {
42             printf("Case %d: -1
", d++);
43             continue;
44         }
45         sort(p, p + n, cmp);
46 
47         double End = p[0].r;
48         int cnt = 1;
49         for (int i = 1; i<n; i++)
50         {
51             if (End<p[i].l)
52             {
53                 cnt++;
54                 End = p[i].r;
55             }
56         }
57         printf("Case %d: %d
", d++, cnt);
58     }
59 }

View Code