TopCoder

Thumb ya2
赤ずきんチャチャ
もっと心の中を二人見せ合えたなら 答えはつかめるよ

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

40.0% (4/10)

Description

題目在這裡

Dark Kingdom 中的一片草原上,DarkKnight 養了很多隻王國最珍貴的黑馬。
有一天,Dark Kingdom 發生地震,於是馬兒開始四處逃竄,為了防止王國珍貴的黑馬消失,DarkKnight 派他底下的士兵來擋住這些馬。

首先 DarkKnight 先用他的原力暫時讓這些馬停下來,但是馬實在太多了,不能維持很久,士兵們必須趁這段時間去卡住適當的位置,讓這些馬完全無法移動。

為了減輕士兵們的負擔,DarkKnight 在東北方放很多黑馬最喜歡的飼料,於是聞到飼料的馬就只會往東北方移動,這樣大大的減輕了士兵的負擔。

最後最重要的是,這些黑馬既然是 DarkKnight 飼養的,想必只會走馬步。
例如如果有一隻黑馬在(1,1)的位置, 有另一隻黑馬在(1,2)的位置(這在(1,1)的北方),然後另外有一個士兵在(3,2)的位置(這在(1,1)的東北方),那麼位在(1,1)的黑馬就不會移動了,因為(1,2)拐到馬腳,(3,2)又擋到路。

現在給你所有黑馬的位置,請問 DarkKnight 要讓所有黑馬無法移動,需要幾名士兵?

Input Format

輸入包含多組測試資料。第一行是一個正整數 n(1≦n≦100000), 表示黑馬的個數, 接下來有 2n 個正整數,x1,y1,x2,y2,...,xn,yn,每個(xi,yi)表示第 i 隻馬的座標,所有座標都位在 1~1000 之間。

Output Format

輸出一行正整數,表示至少需要幾個士兵。

Sample Input

8
1 1 2 2 3 3 4 4 1 3 3 1 2 4 4 2

Sample Output

6

Hints

2015/8/1 將連結的內容搬到網頁上

Problem Source

原TIOJ1132 / [KSHSVC] 雄中公假社'07 公開賽。Problem Setter:Darkseer。

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1