d055. P-4-14. 控制點 (2D-max)

Content

平面上有 $ N $ 個點，第 $ i $ 點的座標為 $(x[i]$ , $ y[i])$ 。若 $ x[i]≤x[j] $ 且 $ y[i]≤y[j]$ ，則我們說第 $ j $ 點可以控制第 $ i $ 點。我們希望能在輸入的點中，選取最少的點做為控制點，使得每一個輸入的點都至少被一個控制點所控制。

輸入 $ N $ 個點的座標，請計算出最少要選取多少個控制點。

Input

每筆測試資料的第一行為一個正整數 $ N，N$ $ $<=$ $ $1e5$ 。

第二行有 $ N $ 個非負整數，依序是這些點的 $ X $ 座標，

第三行有 $ N $ 個非負整數，依序是這些點的 $ Y $ 座標，

座標值不超過 $ 1e9$ 。

Output

輸出最少的控制點數量。

Sample Input #1

4
1 2 3 3
1 2 3 3

Sample Output #1

Sample Input #2

8
3 1 5 3 4 7 8 9
8 2 5 1 2 4 2 3

Sample Output #2

測資資訊：

記憶體限制： 64 MB
不公開測資點#0 (20%): 1.0s , <10M
不公開測資點#1 (20%): 1.0s , <10M
不公開測資點#2 (20%): 1.0s , <10M
不公開測資點#3 (20%): 1.0s , <10M
不公開測資點#4 (20%): 1.0s , <10M

Hint ：

Tags:

sweep line

出處:

AP325 [管理者：

TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」