OJ Board

Can someone tell me the intermediate distances between the polygons and rivers? I think my distance function is off a bit..

I get:
2.353394 3.000000 1.488417
for the 3 red lines..

Larry, I got different result on the middle red line:

upper red-line -> 2.353394
middle red-line -> 2.414039
bottom red-line -> 1.488417

-turuthok-

Thanks, I got AC.. I swapped i and j in one of the calculations.. =)

Call the distance between an edge E and a vertex V[j] Dist(E,V[j]), where E and V[j] don't necessarily belong to the same polygon.

Then the distance between a polygon P[k] and a vertex V[j] is:

Dist(P[k],V[j]) = Min{over all E of P[k]}(Dist(P[k].E,V[j]))

Then the distance between two polygons P[k] and P[k'], with vertices P[k].V[j] and P[k'].V[j'] resp. is:

Dist(P[k],P[k']) = Min(Min{over all V[j] of P[k]}(Dist(P[k'],P[k].V[j])),Min{over all V[j'] of P[k']}(Dist(P[k],P[k'].V[j'])))

I'll bet you can work out Dist(E,V[j]) yourself

The two riverbanks (P[1] and P[2]) aren't exacly polygons, but they can be treated similarly.

Now the distance between two polygons P[a] and P can be shortened if there is a third polygon P[c] so that:

Dist(P[a],P[c]) + Dist(P[c],P) < Dist(P[a],P)

You can use a well known algorithm to iterate over all (a,b,c) and ultimately find the shortest distance between P[1] and P[2].

PS. Keep it a secret, cause I think it's a spoiler...

To give a shorter hint, think of it as a graph problem.. what are you trying to accomplish? What are the edges, nodes, and the weights on the edges?

I guess this is a more general hint, while joey's hint is more specific - I wish I post mine before his.. =)

Well, if you think it's too specific, I'll remove it in a couple of days.
I think my hint concerns the first part of the problem (calculating distances), while your hint is more re the optimization part of the problem (finding the minimum).

Let me know.

hehe, it's not too specific, it's a good hint, just that it would've been nicer if they read my hint first, so that if they're still struck, they can look at your hint.. =)

This is a really nice problem. It looks overwhelming at first ... but when you relax a little bit, ... it actually goes down to "distance between 2 segments" problem.

I got the segment-segment distance from http://www.softsurfer.com ...

-turuthok-

It's a Jimmy Mardell problem, heh, which is usually insanely impossible, so ya.. it isn't so bad once you think about it..

Hey, should I take that as a compliment or not? I've done a couple of easier problems lately...

River Crossing I thought very neat because what you maybe at first sight want is distance between two line segments which, of course, reduces to the distance between one line segment and one point. Originally I only had two river banks, but thought it cool with some islands to add an extra (but still simple) element to the problem.

Can anyone give me some testdata?
I got many WA.
THANKS!

The stupid mistake I made was to only count distances between line segments A1-A2, A2-A3, ... A(n-1)-An. You should take An-A1 into account too. (where A is an array of vertices of an island)