01328: Radar Installation

greedy, http://cs101.openjudge.cn/practice/01328/

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

输入

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

输出

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.

样例输入

样例输出

Case 1: 2
Case 2: 1

来源: Beijing 2002

映射到x轴，排序，左右端点互相看看。程序逻辑解释：

计算岛屿的覆盖区间：对于每个岛屿，先根据其x和y坐标计算出在x轴上的区间范围。这是通过 $\sqrt{d^{2} - y^{2}}$ 来确定的。
排序：将所有岛屿的区间按照右端点进行排序，目的是尽可能让新的雷达覆盖更多的岛屿。
更新覆盖范围：逐个岛屿进行遍历，尝试更新当前雷达能够覆盖的最远点。如果当前岛屿的左端点在已经覆盖的区间之外，则必须增加一个新的雷达，并将新的覆盖范围设为当前岛屿的区间。

python

import math

def solve(n, d, islands):
    if d < 0:
        return -1

    ranges = []
    for x, y in islands:
        if y > d:
            return -1
        delta = math.sqrt(d * d - y * y)
        ranges.append((x - delta, x + delta))

    if not ranges:
        return -1

    ranges.sort(key=lambda x:x[1])

    number = 1
    r = ranges[0][1]
    for start, end in ranges[1:]:
        if r < start:
            r = end
            number += 1

    return number

case_number = 0
while True:
    n, d = map(int, input().split())
    if n == 0 and d == 0:
        break

    case_number += 1
    islands = []
    for _ in range(n):
        islands.append(tuple(map(int, input().split())))

    result = solve(n, d, islands)
    print(f"Case {case_number}: {result}")
    input()

23生科-蔡奕鑫，如果按左边界升序写，小于等于时候也要更新当前最小的右边界。

python

import math

def solve(n, d, islands):
    if d < 0:
        return -1

    #
    ranges = []
    for x, y in islands:
        if y > d:
            return -1
        delta = math.sqrt(d * d - y * y)
        ranges.append((x - delta, x + delta))

    #
    ranges.sort(key=lambda r: r[0])

    #
    cnt = 0
    last_covered = float('-inf')
    for start, end in ranges:
        if start > last_covered:
            cnt += 1
            last_covered = end
        else:
            last_covered = min(last_covered, end)

    return cnt

case_number = 1
while True:
    n, d = map(int, input().split())
    if n == 0 and d == 0:
        break

    islands = []
    for _ in range(n):
        islands.append(tuple(map(int, input().split())))

    result = solve(n, d, islands)
    print(f'Case {case_number}: {result}')
    case_number += 1
    input()

01328: Radar Installation ​

01328: Radar Installation