【POJ-1328】解题报告（二维转一维，贪心）

原始题目

Radar Installation

  • Time Limit: 1000MS
  • Memory Limit: 10000K
  • Total Submissions: 96097
  • Accepted: 21364

Problem 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 \le n \le 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

Source

Beijing 2002

题目大意

给定二维平面N个点的坐标作为小岛坐标，给定雷达辐射半径，求坐标轴上放置雷达的最少个数。

解题思路

将小岛在二维平面钟的坐标转化为一维坐标轴上的线段也即数轴上的闭区间。两个闭区间的交集表示可以同时辐射到这两个小岛的雷达可放置的区域。

由此，要使放置雷达的个数最少。将线段按左端点递增排序，采用贪心策略，对于下一个小岛能利用之前的雷达就利用，条件为，下一条线段的左端点小于公用范围（线段）右边界。否则雷达+1，并以该线段作为新雷达的公用范围。

注意：1.共用范围（线段）是不断减小的，后一条线段的有端点大于共用范围右端，则无影响，若小于右端，则新右边界变为该线段的右端点。

解题代码

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#define maxn 10010
using namespace std;
struct line
{
	double left;
	double right;
}island[10002];

bool cmp(struct line s1,struct line s2)
{
	return s1.left<s2.left;
}

int main()
{
//	freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
	int ni,nd;
	scanf("%d%d",&ni,&nd);
	int count=0;
	while(ni||nd)
	{
	bool flag=false;
	for(int i=0;i<ni;i++)
	{
		double x,y;
		scanf("%lf%lf",&x,&y);
		if(y>nd)
			flag=true;
//		printf("x=%lf y=%lf\n",x,y);
		island[i].left=x-sqrt(nd*nd-y*y);
		island[i].right=x+sqrt(nd*nd-y*y);
	}
	if(flag)
	{
		printf("Case %d: -1\n",++count);
		scanf("%d%d",&ni,&nd);
	}
	else
	{
		sort(island,island+ni,cmp);
//		for(int i=0;i<ni;i++)
//			printf("island[%d] left=%lf right=%lf\n",i,island[i].left,island[i].right);
	int num=1;
	double minright=island[0].right;
	for(int i=0;i+1<ni;i++)
	{
		if(island[i+1].left<=minright)
		{
			if(island[i+1].right<minright)
			{
				minright=island[i+1].right;
			}
		}
		else
		{
			num++;
//			printf("num++\n");
			minright=island[i+1].right;
		}
	}
	printf("Case %d: %d\n",++count,num);
	scanf("%d%d",&ni,&nd);	
	}
	}
//	fclose(stdin);//关闭文件  
//    fclose(stdout);//关闭文件 
	return 0;
}

收获与反思

二维问题转一维，学习一下。