10709 - Intersection is Not that Easy

Larry · Post by **Larry** » Mon Aug 30, 2004 5:59 pm

I try solving it by breaking down into cases, but get WA.

Can anyone provide some insightful input/output? Thanks.

I handled the parallel lines, is there more trick cases?

liulike · Post by **liulike** » Mon Aug 30, 2004 7:08 pm

I need help too

Maniac · Post by **Maniac** » Mon Aug 30, 2004 8:13 pm

did you think about 2 linepieces which are not parallel but do not intersect?
Or one line and a linepiece which are not parallel and do not intersect?

Good luck, Erik

Larry · Post by **Larry** » Mon Aug 30, 2004 9:31 pm

Yes. I don't think they are trick cases..

Maniac · Post by **Maniac** » Tue Aug 31, 2004 2:00 am

well, what I do is pretty straight forward, no exceptions for trick cases made:

if LS and LS
if intersect then distance = 0
else distance is minimum of 4 distances between endpoints

if LS and L
if intersect then distance = 0
else distance is minimum of 2 distances of endpoints of LS to the line

if L and L
if intersect then distance = 0
else distance is distance of any endpoint of first line to the second line

All I need are the right formula's for distance(point,point), distance(point, line) and for intersections between linesegments and lines. For example, 2 line segments intersect if and only if for both segments it holds that the end points of the second line segments lie on different sides of the first line segment. But I don't know whether this helps you out....

liulike · Post by **liulike** » Tue Aug 31, 2004 4:23 am

Maniac wrote:well, what I do is pretty straight forward, no exceptions for trick cases made:

if LS and LS
if intersect then distance = 0
else distance is minimum of 4 distances between endpoints
....

How to explain the second sample?
The minimum of 4 distances between endpoints is 1.414***, not the 0.27735 which is the sample output.

Larry · Post by **Larry** » Tue Aug 31, 2004 4:46 am

Maniac: that is exactly how I implemented it.

I think I'll rewrite it sometime.. I don't think precision should be a problem, but it appears to be the case otherwise..

Thanks for your help.

abishek · Post by **abishek** » Tue Aug 31, 2004 7:31 am

i think the idea of maniac is wrong for the LS LS case.
the line segments may have a perpendicular distance, less than the distance between the end points.
as i have not yet solved this problem, i got this idea reading the board, i will try and tell you if i get AC
abi

abishek · Post by **abishek** » Tue Aug 31, 2004 7:53 am

consider the case when the Line segments are the parallel sides of a trapezium.
i think that will give a test case where maniacs idea will fail.

Maniac · Post by **Maniac** » Tue Aug 31, 2004 11:12 am

whoops! You're totally right abishek and liulike. I took a (too) quick look at my AC solution. This indeed should not be 'distance is minimum of 4 distances between endpoints' but 'distance is minimum of 2*2 distances between linesegments and endpoints'. Sorry about that....

Larry · Post by **Larry** » Tue Aug 31, 2004 1:09 pm

I thought that's what you meant. I just reused the code from River Crossing..

liulike · Post by **liulike** » Tue Aug 31, 2004 8:19 pm

I got AC at last

Thanks every one!

dll · Post by **dll** » Mon Sep 06, 2004 10:42 am

anyone gives some IO?
I got WA WA...

liulike · Post by **liulike** » Mon Sep 06, 2004 6:05 pm

There is no trick i/o!

Check your program

arif_pasha · Post by **arif_pasha** » Mon Sep 06, 2004 9:52 pm

can anyone give some i/o
i am getting wa all the time

for this input

10 10 11 11 L
15 15 19 19 L
0 0 10 0 L
5 5 10 5 L
0 0 1 1 L
-1 1 2 -2 L
0 0 10 0 L
0 0 0 10 L
2 2 5 5 LS
0 3 8 3 L
2 2 5 5 L
0 3 8 3 LS
0 3 8 3 L
5 5 15 15 LS
-8 0 -1 0 LS
0 1 5 5 LS
-8 0 0 8 LS
0 8 0 -8 LS
0 0 10 0 LS
2 2 8 8 LS
0 5 5 0 LS
0 5 5 5 LS
5 6 8 9 LS
1 1 3 9 LS
5 8 5 6 LS
7 7 100 -2 LS
5 5 6 9 END
5 8 6 4 END

my program produces:

0.00000
5.00000
0.00000
0.00000
0.00000
0.00000
2.00000
1.41421
0.00000
0.00000
0.00000
2.66789
2.00000