a533. IOI2004 Day1.1.阿特米斯
標籤 :
通過比率 : 33人/39人 ( 85% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-11-01 02:06

內容

    宙斯給森林女神阿特米斯一塊矩形土地種植樹木。這塊矩形土地的左邊位於正Y軸,下邊位於正X軸,左下方位於(0,0)原點。宙斯告訴阿特米斯神樹木只能種在矩形土地內的的整數點上。阿特米斯神希望森林看起來非常自然,所以她種樹的時候會注意任何兩棵樹的連線都不會與X軸或Y軸平行。

    宙斯有時候會請阿特米斯神依下列條件為他砍樹:

1.      宙斯希望至少要砍T棵樹。

2.      宙斯希望提倡足球運動,所以阿特米斯神必須將一矩形區域內的所有樹都砍倒,同時不能砍任何位於該區域外的樹。

3.      此矩形區域的每一邊都與X軸或Y軸平行。

4.      此矩型區域的一組對角必須位於樹的位置上,而且這兩棵位於對角的樹也必須砍除。

    阿特米斯神非常喜歡樹,所以她希望以砍倒最少的樹來滿足上數條件。請寫一個程式,從樹木種植情形及給定之最少需砍數目棵樹T,找出此矩形區域。

輸入說明
    輸入第一行為一整數N,代表森林中的樹木棵數。第二行為一整數T,代表需砍倒的最少數目棵數。之後的N行紀錄樹的位置。第一行有兩個整數X及Y,代表樹位置的X及Y座標。X座標在Y座標之前。
輸出說明

    輸出只有一行,包含兩個以一空白隔開的整數I及J。阿特米斯神會使用第I棵(輸入的第I+2行)及第J棵樹(輸入的第J+2行)作為砍樹矩形區域的兩個對角。選取區域的最佳方法可能超過一種,但你只需輸出其中一種,I及J的輸出順序不重要。每一組測試資料都存在至少一組解。

為了judge方便,請只輸出最少要砍倒幾棵樹的數量

 

範例輸入 #1
範例輸入1
3
2
1 1
2 3
5 6

範例輸入2
6
4
5 1
1 2
4 3
2 4
3 5
6 6
範例輸出 #1
範例輸出1
2

範例輸出2
5

測資資訊:
記憶體限制: 512 MB
提示 :

在所有的輸入中,1<N≤20000, 0≤X,Y≤64000 且1<T≤N。

除此之外,在50%的輸入中,1<N<5000。

1.由於當年比賽主機特強,看似不合理的複雜度是可以在1s內過的..

2.ZJ主機特強

3.注意記憶體限制 

標籤:
出處:
IOI2004Day1第一題 [管理者: david942j (文旋) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」