POJ--1328 Radar Installation(贪心)

记录
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;
}