CCC '00 S5 - Sheep and Coyotes

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.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 1000. 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


Sample Output

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


  • 3
    cabbagecabbagecabbage  commented on Feb. 23, 2021, 3:32 p.m.

    I've seen a lot of WA's on this problem (especially on test case 6), many of which have the correct algorithm but WA because of floating point imprecision. For example, with Python 3, you likely will not pass using floats (depending on your algorithm) because they are not accurate enough. To work around this, consider using the decimal module as described here and make sure not to use float() anywhere in your program (although I'm sure there are other workarounds). I'm not sure about other languages.

    Normally I wouldn't leave "hints" in the comments, but to a beginner who has never heard of the concept that computers can't store decimals perfectly accurately, they could potentially waste hours debugging their conceptually correct algorithm in vain. Hope this helps.

    • 0
      myl  commented on Feb. 24, 2021, 8:36 p.m. edited

      For the output, would you still round to 2 decimal places for case 6? And should the rounding be half-up or just truncated? I'm using the decimals module and it's still not working.

      Also why do they have to troll us like this, case 6 wasn't even in the CCC ._.

      • 1
        cabbagecabbagecabbage  commented on Feb. 25, 2021, 11:38 p.m.

        Your mistake is that you're putting l >= r on line 36 in your latest submission, when in fact l == r gives a valid interval. As a side note, I believe they prefer people asking for help on slack instead of the comments to avoid clogging up the comment section.

  • 0
    myl  commented on Feb. 22, 2021, 11:37 p.m.

    Why do I always get test case 6 wrong?

    • -1
      goomba  commented on Feb. 23, 2021, 3:09 p.m.

      This problem has one of the lowest AC rates of the CCC problems. I'd suggest trying an easier one.

      • 1
        myl  commented on Feb. 24, 2021, 8:30 p.m. edited

        Honestly, the problem itself is not all that hard, it's just that test case 6 is kind of trolly

        Test case 6 is not on the CCC btw

  • 1
    tortle  commented on Nov. 28, 2020, 11:24 a.m.

    It's possible for multiple sheep to have the same coordinates right? And we have to output whether they might be eaten for each of them?

  • 2
    Tony1234  commented on Nov. 20, 2020, 12:07 p.m.

    Does the coyote enter anywhere in the "bottom" of the land, the problem does not state where it enters.

  • 1
    KO04  commented on Oct. 29, 2020, 12:01 p.m.

    can somebody help with my code. i got the exactly same answer as the example. but i am keep getting wa from the judgement.

  • 4
    Lynthical  commented on Sept. 7, 2020, 6:44 p.m.

    Did a test case get added to this problem?

    • 5
      Kirito  commented on Sept. 7, 2020, 7:22 p.m.

      We added PEG's additional (anti-brute force) testcase and rejudged all submissions.

      The old cases make up 50/100 points, so only passing the original cases will still give you 10 points on the problem.

      • 3
        Render_Main  commented on Sept. 8, 2020, 9:33 p.m.

        What is the intended time complexity for that test case? O(N^3) solution passed in 0.133s.

        • 4
          Kirito  commented on Sept. 9, 2020, 5:11 p.m.

          DMOJ judges are too fast, we could kill that by making TL go down to 0.05 or something, but then we'd have to tune TLs for other languages and it's not worth the effort.

          There's a hard version for anyone who wants to try their hand at solving the problem with larger constraints.

      • 2
        Dingledooper  commented on Sept. 8, 2020, 1:39 p.m.

        The new test case seems to have something like 1000 sheep; this should be updated in the problem statement.

        • 2
          Zeyu  commented on Sept. 8, 2020, 1:58 p.m.

          Fixed. Thanks for pointing it out :)

  • -7
    harry7557558  commented on March 25, 2020, 9:26 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.

    • 22
      Tomorrow  commented on May 25, 2020, 7:28 p.m.

      For those who keep getting WA on case 5, this picture might be helpful.

      official test case

      Each point represents a sheep. All sheep not colored in green might be eaten.

  • -1
    noYou  commented on March 11, 2020, 4:59 p.m.

    Why am I getting wa for all cases? I checked the official test data, and my program matches the expected output?

    • 2
      Togohogo1  commented on March 11, 2020, 11:27 p.m. edited

      Make sure to format your output to 2 decimal places.

  • 3
    45628andy  commented on Feb. 6, 2019, 1:54 a.m.

    Still confused by case 5... Any hint will be appreciated

  • 6
    AntonyVer2  commented on Nov. 17, 2018, 5:01 p.m.

    Can someone shed some light on case 5?

    • -4
      hfanalytica  commented on Feb. 27, 2019, 12:26 p.m.


      • -17
        Roronoa_Zoro1540  commented on Feb. 1, 2020, 8:47 p.m.

        This comment is hidden due to too much negative feedback. Click here to view it.

  • 26
    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'?

  • 2
    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.

    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?

    • 15
      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.

  • 7
    onlyIfStatement  commented on Jan. 3, 2017, 10:53 a.m.

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