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

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

內容

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

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

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

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

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

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

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

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

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

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

 

範例輸入
範例輸入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
2

範例輸出2
5

測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 1.0s , <1M
公開 測資點#1 (5%): 1.0s , <1M
公開 測資點#2 (5%): 1.0s , <1M
公開 測資點#3 (5%): 1.0s , <1M
公開 測資點#4 (5%): 1.0s , <1M
公開 測資點#5 (5%): 1.0s , <1M
公開 測資點#6 (5%): 1.0s , <1M
公開 測資點#7 (5%): 1.0s , <1M
公開 測資點#8 (5%): 1.0s , <1M
公開 測資點#9 (5%): 1.0s , <1M
公開 測資點#10 (5%): 1.0s , <1M
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <1M
公開 測資點#14 (5%): 1.0s , <1M
公開 測資點#15 (5%): 1.0s , <1M
公開 測資點#16 (5%): 1.0s , <1M
公開 測資點#17 (5%): 1.0s , <1M
公開 測資點#18 (5%): 1.0s , <1M
公開 測資點#19 (5%): 1.0s , <1M
提示 :

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

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

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

2.ZJ主機特強

3.注意記憶體限制 

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


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