记录
0:50 2023-5-1
http://poj.org/problem?id=1328
reference:《挑战程序设计竞赛(第2版)》第二章练习题索引 p135
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
3 2
1 2
-3 1
2 1
1 2
0 2
0 0
Sample Output
Case 1: 2
Case 2: 1
贪心，我一开始的思路是错误的。一开始想先将点从左到右排序起来，让后寻找可以覆盖这个点的雷达，越右边越好，这样可以尽可能的覆盖多的点。这样想是不对的，用的雷达会多。
合理的做法是，以岛为中心画圆，和x轴有最多俩个交点，这个区间(使用一元二次函数准确计算为实数)内的点都是可以选的，将所有岛对应的区间算出来，排序后计算重叠的局域，有多少个重叠的区域就有多少的个解。
注意：求重叠区域后需要将判断的范围缩小到重叠区域
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<utility>
#include<cmath>
using namespace std;
#define MAX_N 1000
typedef long long ll;
typedef unsigned int uint;
const int INF = 0x3f3f3f3f;
typedef struct {
int x;
int y;
} P;
typedef struct {
float x;
float y;
} Q;
P v[MAX_N + 1];
int k = 0;
Q region[MAX_N + 1];
int N, D;
int Case = 1;
bool comp(Q lhs, Q rhs) {
return (lhs.x < rhs.x) || (lhs.x == rhs.x && lhs.y > rhs.y);
}
void solve() {
int result = N;
k = 0;
for(int i = 0; i < N; i++) {
int x = v[i].x;
if(D <= 0 || v[i].y < 0) {
result = -1;
break;
}
float a = 1, b = -2 * v[i].x, c = v[i].x * v[i].x + v[i].y * v[i].y - D * D;
Q q;
q.x = (-b - sqrt(b * b - 4 * a *c)) / (2 * a);
q.y = (-b + sqrt(b * b - 4 * a *c)) / (2 * a);
if((b * b - 4 * a *c) < 0) {
result = -1;
break;
}
region[k] = q;
k++;
}
if(result != -1) {
sort(region, region + k, comp);
for(int i = 0; i < k; i++) {
float x1 = region[i].x, y1 = region[i].y;
while (i + 1 < k) {
float x2 = region[i + 1].x, y2 = region[i + 1].y;
if(y1 >= x2) {
result--;
x1 = max(x1, x2);
y1 = min(y1, y2);
i++;
} else {
break;
}
}
}
}
printf("Case %d: %d\n", Case, result);
Case++;
}
int main() {
while (~scanf("%d %d", &N, &D)) {
if(N == 0 && D == 0) break;
for(int i = 0; i < N; i++) {
scanf("%d %d", &(v[i].x), &(v[i].y));
}
solve();
}
return 0;
}