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


提交答案

分數: 100 (部分)
時間限制: 1.0s
記憶體限制: 1G

作者:
題目類型

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

輸入格式

每筆測試資料的第一行為一個正整數 NN <= 1e5 。 第二行有 N 個非負整數,依序是這些點的 X 座標, 第三行有 N 個非負整數,依序是這些點的 Y 座標, 座標值不超過 1e9

輸出格式

輸出最少的控制點數量。

範例輸入一

複製
4
1 2 3 3
1 2 3 3

範例輸出一

複製
1

範例輸入一

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

範例輸出一

複製
4

留言

目前沒有評論。