TIOJ 1404 照亮的山景

Description

在一片山的上空，高度為 $t$ 處有 $n$ 個處於不同水平位置的燈泡，如上圖所示。

如果山的邊界上某一點與第 $i$ 盞燈的連線不經過任何山稜線上的一點，我們稱第 $i$ 盞燈可以照亮該點。

請問至少要打開幾盞燈，才能照亮山上每一個轉折點？

Input Format

輸入可能包含多筆測試資料。

對於每筆測試資料：

第 $1$ 列：一個整數 $m$ ($1\leq m\leq 100,000$)，代表山稜折線的轉折點個數。

第 $2$ ～ $m+1$ 列：$x_i, h_i$，依序代表轉折點的水平座標以及垂直海拔高度。($-100,000\leq x_i, h_i\leq 100,000$)

所有轉折點座標將以 $x$ 座標由小到大排列。

第 $m+2$ 列：$n, t$，其中 $n$ 代表燈泡個數，$t$ 代表所有燈泡的高度，該高度必定高於整座山最高轉折點的高度。

($1\leq n, t\leq 100,000$)

第 $m+3$ 列：有 $n$ 個整數 $b_1, b_2, \ldots,  b_n$，代表 $n$ 個燈泡的水平座標，且依座標值由小到大排列。

Output Format

如果可以點亮某幾盞燈而照亮所有轉折點，請輸出最少需要點亮的燈泡數量。

否則請輸出 "you need more bulbs!"(不包含雙引號)。

Sample Input

6

1 1

3 3

4 1

7 1

8 3

11 1

4 5

1 5 6 10

6

1 1

3 3

4 1

7 1

8 3

11 1

2 5

1 5

Sample Output

2

you need more bulbs!

Solution

首先，不難發現某個轉折點能被照到若且唯若有顆燈泡的位置在水平線 $y=t$ 上的某個開區間內。如果我們能求出每個轉折點對應的開區間，問題就被轉成下面這個形式：給定 $\mathbb{R}$ 上的 $m$ 個開區間 $\{(l_i, r_i)\}_{i=1}^m$，從 $b_1, \ldots, b_n \in \mathbb{R}$ 中選出最少的點使得每個區間至少包含一個被選中的點。這個問題有個簡單的貪婪解法，可以在 $O(m\log m+n)$ 時間內解決。

那麼要怎麼算出每個轉折點對應的開區間呢？假定我們想算 $P_i := (x_i, h_i)$ 的左界 $l_i$，只要找到 $1 \leq j \leq i-1$ 使得 $\overline{P_jP_i}$ 的斜率最小就行了。可以發現，這個 $P_j$ 必定在「$P_1, \ldots, P_{i-1}$ 形成的上凸包 (upper convex hull) 邊界」上；此外，「某個 $j=j^*$ 最小化 $\overline{P_jP_i}$ 的斜率」，若且唯若「$\overline{P_{j^*}P_i}$ 在『$P_1, \ldots, P_i$ 形成的上凸包邊界』上」，也就是 $l_1, \ldots, l_m$ (以及 $r_1, \ldots, r_m$) 可由 Andrew's 演算法在 $O(m)$ 時間內求得。

最佳解 $P_{j^*}$ 在上凸包邊界 (紅色) 上，且 $\overline{P_{j^*}P_i}$ (藍色) 成為新上凸包邊界的一部份。

我的 code：
https://ideone.com/z7J87D

以下雜談。其實這題原本和出處 CEOI 2000 Problem 6 一樣，要求照亮整座山 (包含稜線)，而照亮所有的轉折點並不能保證這件事情 (why?)；不幸的是，刘汝佳的《算法艺术与信息学竞赛》裡面的解法，也只考慮了所有的轉折點是否被照亮 (因此也是假解)。我在向 TIOJ 管理員反應了這件事後，他就修正題目敘述了www。

那麼考慮原始題目 $m, n \leq 200$，有沒有一個好的正解呢？我有想到一個 $O(mn \log(mn))$ 時間複雜度的做法，只是稍嫌麻煩，等某天我上傳題目至 ZJ 後再來介紹。