CCC '00 S5 - Sheep and Coyotes (Hard)

View as PDF

Submit solution

Points: 20
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
Canadian Computing Competition: 2000 Stage 1, Senior #5

A square 10^6 by 10^6 field contains several sheep. A coyote enters the field at some point in the south boundary and proceeds to eat the sheep closest to the point of entry, picking arbitrarily if more than one sheep is equally close. The coyote, being sated, then leaves the field.

Your job is to determine which sheep may be eaten by the coyote.

Assume that the southwest corner of the field is located at (0, 0), the northwest corner at (0, 10^6), the northeast corner at (10^6, 10^6) and the southeast corner at (10^6, 0).

Note: The constraints have changed from the original problem.

Input Specification

The first line of input gives the number of sheep, between 1 and 10^5 inclusive. For each sheep a pair of lines follows, giving its integer coordinates within the field (between 0 and 10^6 inclusive).

Output Specification

For each sheep that might be eaten print a line The sheep at (x, y) might be eaten. where x and y give the location of the sheep. The sheep can be listed in any order in the output.

Sample Input


Sample Output

The sheep at (100, 100) might be eaten.
The sheep at (300, 100) might be eaten.


There are no comments at the moment.