TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

58.3% (14/24)

Submission's AC Ratio

16.2% (28/173)

Tags

Description

在一片山的上空,高度為T處有N個處於不同水平位置的燈泡,如上圖所示。
如果山的邊界上某一點與第i盞燈的連線不經過任何山稜線上的一點,我們稱第i盞燈可以照亮該點。
請問至少要打開幾盞燈,才能照亮山上每一個轉折點?

Input Format

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

對於每筆測試資料:


第1列:一個整數M (1<=M<=100,000),代表山稜折線的轉折點個數。

第2~M+1列:Xi Hi,依序代表轉折點的水平座標以及垂直海拔高度。(-100,000<=Xi, Hi<=100,000)
所有轉折點座標將以X座標由小到大排列。

第M+2列:N T,其中N代表燈泡個數,T代表所有燈泡的高度,該高度必定高於整座山最高轉折點的高度。
(1<=N, T<=100,000)

第M+3列:有N個整數 B1 B2 ... BN,代表N個燈泡的水平座標,且依座標值由小到大排列。

Output Format

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

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

Sample Input 1

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 1

2
you need more bulbs!

Hints

在第一筆範例測試資料中,選擇位置為1以及6的兩個燈泡,即可照亮每個轉折點。

Problem Source

原TIOJ1404 / 快樂暑假第四次練習比賽。Problem Setter:Tmt。
(Adapted From CEOI 2000 Problem 6, 算法藝術P.13)
題目修正by hiiragi4000

Subtasks

No. Testdata Range Score
1 0 12
2 1 12
3 2 12
4 3 12
5 4 12
6 5 12
7 6 12
8 7 16

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
2 10000 65536 262144 3
3 10000 65536 262144 4
4 10000 65536 262144 5
5 10000 65536 262144 6
6 10000 65536 262144 7
7 10000 65536 262144 8