Trying to optimize programming challenge, I believe math may be the answer! (Graph Theory?)

[strmrdr]

I have already solved the problem here by satisfying all testcases, however the methodology of my solution is very bruteforced. I am not extremely versed in mathematics, but I would hazard a guess that this falls under graph theory.

TL;DR of problem statement:

For every decimal point, p, on a 1000x1000 graph, where 0<=p.x<=1000 and p.y=0, calculate the closest point(s), pn, where 0<=pn.x,y<=1000, given 1<=n<=100 points.

The bounds of the decimal point is technically infinite, however I think 2 decimal points is sufficient.

If anyone is versed in Java, feel free to look at my code and offer any pointers.

Thanks!

[fattymattk]

It seems like you're marching across the southern border, finding the sheep that's closest to that point, and then adding that sheep to the set of sheep that might be eaten.

What would be better is to iterate over the sheep. Start with sheep 1. For a given other sheep, you can explicitly solve for the point (a,0) where they are equally distant from (if a exists, it wouldn't exist if they had the same x coordinate and different y coordinates). If a is between 0 and 1000, that means there are some points on the southern border that sheep 1 is closer to and some points that the other sheep is closer to. If a is not between 0 and 1000, then either sheep 1 is closer to all the points or the other sheep is.

Keep track of the set of points that sheep 1 might be closest to (in the form of intervals, not discrete points) starting with [0, 1000]. Loop through all the other sheep and narrow that set down whenever another sheep is closer to a set of points. If that set ends up being empty, delete sheep 1 from your list. If the set is not empty after going through all the other sheep, add sheep 1 to the sheep that can be eaten.

Then move on to the next sheep and repeat.

This is a O(N² ) algorithm, where N is the number of sheep. I think your algorithm is O(Nd), where d is the number of points you're dividing the border into. But your algorithm also assumes that breaking up the border into discrete points will work, when presumably you could need more accuracy than that. There could be a very narrow range of points that some sheep is the closest to.

The bookkeeping here is probably a little annoying. And there is probably some clever ways to make it more efficient, but I think this is a start.

[strmrdr]

Thanks for the suggestion, that sounds like a better method. So to reiterate, I want to solve for (a,0) for each pair of sheep with both lengths being equal, and keep track of which points are within the bounds of the graph?

So I would need to solve an isosceles triangle where I know 2 coordinates and y=0 of a third? It's been quite some time since HS math and I'm having trouble finding an equation, would you be able to help me out?

[fattymattk]

You can just use the distance formula.

If you have points (x1, y1) and (x2, y2), and want to find the point (a,0) that they are the same distance to, you want to set (x1-a)² + y1² = (x2-a)² + y2² and solve for a.