OJ Board

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?

I need help too

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

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

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

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.

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.

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

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.

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

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

I got AC at last

Thanks every one!

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

There is no trick i/o!

Check your program

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