2000 Canadian Computing Competition, Stage 1

Problem S5: Sheep and Coyotes

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). 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).

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.

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Oct 01, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

The last case is extremely tricky, and has [b]1000[/b] sheep.
Again this will be a 20 point problem, so no points lost.

ty for info

This more than 3 year old post didn't need to be bumped/replied to.

bump

Any advice for the last case?

My advice is: find an O(N^2) algorithm

I think I found one, it just doesn't seem to be working for the last case...

My O(n^2) algorithm gave trouble on the last case due to precision errors.

Any advice for precision because my solution seems to be messing up on that?

Well the mistake I made was with a comparison operator. I accidentally used a < instead of a <=. Maybe check those and see if it works?

I used the <= operator with an epsilon :/

so basically find the dis and the shortest one is eaten right?

See dAedaL's post below, titled "We don't," or bbi5291's post "Re: When (as an example) would the x coordinate matter)."

Couldn't we just find the distance from every sheep to every point from 1-1000 and check the smallest in each of them or would that time out?

The coyote isn't restricted to entering at integer x-coordinates, though, it could enter at a point like 577.215665. You could obtain a better approximation by taking smaller steps (like 0.01, 0.02, 0.03, etc.) but Hanson carefully crafted one of the test cases so that the resolution required would take too much time.

I can't think of a scenario where the x coordinate would matter for this program.

The problem statement is not always easy to understand. What it is saying is that the coyote may choose [i]any[/i] point on the fence, and then it locates the closest sheep to its [b]current location[/b].

But then, since it could choose any spot, how would the x co-ordinate be of any use? Besides the fact that they are ON the fence ...

No, no, that's not it. Assume that the coyote enters randomly at some point on the fence. Then the coyote finds the sheep closest to its current location.

In other words, a sheep can be eaten if there exists at least one point on the fence such that the distance from that point to this sheep to this point is less than or equal to the distance from that point to any other sheep.

Just try two random points with a similar y-coordinate.
For example, (0, 10) and (1000, 11).

Obviously if the wolf comes in at coordinate 0 it's going to eat the first one, but if it comes in at coordinate 1000 it's going to eat the second one. Both sheep are "edible".

nop.e that'll get you 40/50

How exactly do we know where along the soutern boundary the coyotes is going to enter? Is it relative to some other factor?

The coyote can enter at any point along the southern boundary.  Your job is to find which sheep may be eaten.  I guess it can be viewed that he enters from ALL points along the boundary.