宙斯給森林女神阿特米斯一塊矩形土地種植樹木。這塊矩形土地的左邊位於正Y軸,下邊位於正X軸,左下方位於(0,0)原點。宙斯告訴阿特米斯神樹木只能種在矩形土地內的的整數點上。阿特米斯神希望森林看起來非常自然,所以她種樹的時候會注意任何兩棵樹的連線都不會與X軸或Y軸平行。
宙斯有時候會請阿特米斯神依下列條件為他砍樹:
1. 宙斯希望至少要砍T棵樹。
2. 宙斯希望提倡足球運動,所以阿特米斯神必須將一矩形區域內的所有樹都砍倒,同時不能砍任何位於該區域外的樹。
3. 此矩形區域的每一邊都與X軸或Y軸平行。
4. 此矩型區域的一組對角必須位於樹的位置上,而且這兩棵位於對角的樹也必須砍除。
阿特米斯神非常喜歡樹,所以她希望以砍倒最少的樹來滿足上數條件。請寫一個程式,從樹木種植情形及給定之最少需砍數目棵樹T,找出此矩形區域。
輸出只有一行,包含兩個以一空白隔開的整數I及J。阿特米斯神會使用第I棵(輸入的第I+2行)及第J棵樹(輸入的第J+2行)作為砍樹矩形區域的兩個對角。選取區域的最佳方法可能超過一種,但你只需輸出其中一種,I及J的輸出順序不重要。每一組測試資料都存在至少一組解。
為了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
在所有的輸入中,1<N≤20000, 0≤X,Y≤64000 且1<T≤N。
除此之外,在50%的輸入中,1<N<5000。
1.由於當年比賽主機特強,看似不合理的複雜度是可以在1s內過的..
2.ZJ主機特強
3.注意記憶體限制
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|