d055: P-4-14. 控制點 (2D-max)
Tags : sweep line
Accepted rate : 115人/116人 ( 99% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-05-30 20:29

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
1
Sample Input #2
8
3 1 5 3 4 7 8 9
8 2 5 1 2 4 2 3
Sample Output #2
4
測資資訊:
記憶體限制: 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
沒有發現任何「解題報告」