CCC '00 S5 - Sheep and Coyotes

View as PDF

Submit solution


Points: 10
Time limit: 2.0s
Memory limit: 16M

Problem type

Canadian Computing Competition: 2000 Stage 1, Senior #5

A square 1000 by 1000 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.00, 0.00), the northwest corner at (0.00, 1000.00), the northeast corner at (1000.00, 1000.00) and the southeast corner at (1000.00, 0.00).

Input Specification

The first line of input gives the number of sheep, between 1 and 100. For each sheep a pair of lines follows, giving its coordinates within the field (between 0.00 and 1000.00).

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 to two decimal places. The sheep can be listed in any order in the output.

Sample Input

6
100.00
100.00
200.00
150.00
140.00
200.00
100.00
300.00
300.00
300.00
300.00
100.00

Sample Output

The sheep at (100.00, 100.00) might be eaten.
The sheep at (300.00, 100.00) might be eaten.

Comments


  • 1
    Epic1Online  commented on Nov. 16, 2017, 6:11 p.m.

    The question doesn't seem to specify where the coyote enters from other than the southern boundary, does this mean it can enter at any point at the 'bottom'?


  • 0
    rlin264  commented on Aug. 24, 2017, 3:12 p.m.

    Whats is case 5 supposed to be? I keep getting WA for only case 5. Any hints?


  • -1
    septence123  commented on Feb. 7, 2017, 10:32 p.m.
    MLE?

    when I submit in PyPy2 I get MLE, even though it only uses around 5 mb when I submit it in python2? any reason for this?


    • 4
      Xyene  commented on Feb. 8, 2017, 12:45 a.m.

      Yes, the memory limit for this problem is 16M, and even a hello world program uses 30M in PyPy. That's the trade-off between performance and memory usage.


  • 0
    onlyIfStatement  commented on Jan. 3, 2017, 10:53 a.m.
    Float Precision Error?

    Is case 5 testing for a precision error or am i making another mistake?