HBC24853石头剪刀布,贪心[USACO 2009 Nov B]Claustrophobic Cows题解

不断提升技能，才能在职场中立于不败之地！全网最全C++题库，助您成为编程领域的佼佼者。

Farmer John has acquired a set of N (2

Farmer John has acquired a set of N (2 <= N <= 2,000) touchy cows who are conveniently numbered 1..N. They really hate being too close to other cows. A lot. FJ has recorded the integer Xi,Yi coordinates of every cow i (1 <= Xi <= 100,000; 1 <= Yi <= 100,000). Among all those cows, exactly two of them are closest together. FJ would like to spread them out a bit. Determine which two are closest together and print their cow id numbers (i) in numerical order. By way of example, consider this field of cows (presented on a typewriter grid that has slightly different proportions than you might expect): 10 | . . . . . . . 3 . . . . . 9 | . 1 . . 2 . . . . . . . . 8 | . . . . . . . . . . . . . 7 | . . . . . . . . . . 4 . . 6 | . . . . . . 9 . . . . . . 5 | . 8 . . . . . . . . . . . 4 | . . . . . 7 . . . . . . . 3 | . . . . . . . . . 5 . . . 2 | . . . . . . . . . . . . . 1 | . . . . 6 . . . . . . . . 0 --------------------------- 1 1 1 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 Quick visual inspection shows that cows 7 and 9 are closest together (the distance separating them is sqrt(1*1+2*2) = sqrt(5), so the output would be '7 9' on a single line (without quotes, of course).

标签： HBC24853石头剪刀布 贪心[USACO 2009 Nov B]Claustrophobic Cows题解