10709 - Intersection is Not that Easy

windows2k · Post by **windows2k** » Tue Sep 07, 2004 2:55 am

arif_pasha wrote: I pass all the input except this one.
Can you explain this input?
Can you give me more test input/output?
thx
0 0 10 0 LS
2 2 8 8 LS

0.00000

arif_pasha · Post by **arif_pasha** » Tue Sep 07, 2004 9:40 pm

at long last.. ac

thanks to all

whisk · Post by **whisk** » Fri Sep 17, 2004 10:45 pm

What it the correct definition for distance between two non-intersecting line segments? Is it the length of shortest perpendicular dropped from segment endpoint to another segment?

Per · Post by **Per** » Sun Sep 19, 2004 11:47 am

It is the minimal value of dist(p1, p2), where p1 ranges over all points in the first line segment, and p2 ranges over all points in the second line segment.

whisk · Post by **whisk** » Sun Sep 19, 2004 8:03 pm

Thanks. I come from the same consideration but get WA and can't find what's wrong

. Could anyone provide some test data, pls?

alex[LSD] · Post by **alex[LSD]** » Mon Sep 20, 2004 4:08 pm

Hah... Per's post seems really helpful 8-))))
Check out this test :
LS LS
0 0 1 0 // segm 1
2 2 2 -2 // segm 2
Answer = 1

and this one too
LS LS
0 0 1 0
2 1 3 1
Answer = sqrt(2)

whisk · Post by **whisk** » Mon Sep 20, 2004 6:20 pm

2alex[LSD]: Those tests passed fine though your input format seems strange

whisk · Post by **whisk** » Thu Sep 23, 2004 10:19 pm

AC at last. Of course, the trouble was in the input format

There might be more that one space before "L/LS".

DJWS · Post by **DJWS** » Wed Oct 27, 2004 4:41 am

I got WA several times but can't figure out the bugs.

Could someone offer me some test data?

--
DJWS, a newbiw in programming

DJWS · Post by **DJWS** » Wed Oct 27, 2004 8:29 am

I got WA in problem 10514 River Crossing, even my program generated correct answer with the sample input.
(That's also a segment-intersection problem.)

I ponder if I make mistakes somewhere.
So depressed.

--
DJWS, a newbie in programming

DJWS · Post by **DJWS** » Wed Oct 27, 2004 3:56 pm

Finally got AC.

There are some problems that I have confronted:

1. Segment-intersection
I made mistake checking two co-linear segments.

2. Distance from a point to a line
At first I use the formula " |ax+by+c| / sqrt(a^2+b^2) " to calculate the distance, but this may cause precision error when calculating a, b, and c.
I tried to use "vector cross operation", and it works correctly.

3. Distance from a point to a segment
I used "vector dot operation" to determine if perpendicular distance is proper.
If not, the proper distance is just distance between the point and one endpoint of the segment.

Hope it helps someone getting WA.

--
DJWS, a newbie in programming

Larry · Post by **Larry** » Fri Feb 11, 2005 6:47 am

Anyone have more cases? I pass all the one on this board.. is precision an issue?

TISARKER · Post by **TISARKER** » Wed Jun 01, 2005 9:27 pm

I am getting wrong answer again and again.
Please Give me some critical Input.

bijon · Post by **bijon** » Tue Jun 07, 2005 7:29 pm

I cannot find the bug of my code.
please give some input and output data.[/b]

bijon · Post by **bijon** » Tue Jun 07, 2005 7:38 pm

I cannot find error in my code.

please give some input and output data.

OJ Board

10709 - Intersection is Not that Easy

10709 definition

10709(Intersection is not that Easy) Wrong answer