10514 - River Crossing

Larry · Post by **Larry** » Thu Aug 07, 2003 5:29 am

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

Larry · Post by **Larry** » Thu Aug 07, 2003 5:35 am

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

turuthok · Post by **turuthok** » Thu Aug 07, 2003 7:19 am

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-

Larry · Post by **Larry** » Thu Aug 07, 2003 3:24 pm

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

anupam · Post by **anupam** » Fri Aug 08, 2003 2:12 pm

can anyone tell me his algorithm very shortly??
plz help.
Thanks.
--
Anupam

little joey · Post by **little joey** » Fri Aug 08, 2003 3:18 pm

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

Larry · Post by **Larry** » Fri Aug 08, 2003 3:32 pm

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

little joey · Post by **little joey** » Fri Aug 08, 2003 3:40 pm

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.

Larry · Post by **Larry** » Fri Aug 08, 2003 3:58 pm

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

turuthok · Post by **turuthok** » Fri Aug 08, 2003 7:08 pm

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-

Larry · Post by **Larry** » Fri Aug 08, 2003 7:35 pm

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

Yarin · Post by **Yarin** » Sat Aug 09, 2003 2:01 am

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.

anupam · Post by **anupam** » Sat Aug 09, 2003 2:03 pm

oh little joey!
why did you think to remove your post?
a great helper will not tend to do it.
i have found my bug reading your post. and think getting ac soon.
thank you.
--
Anupam

liulike · Post by **liulike** » Sun Sep 14, 2003 10:54 am

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

Whinii F. · Post by **Whinii F.** » Mon Sep 15, 2003 8:31 am

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)