We have got two line.And we know the line's start and end point cordinate. And if they intersect we will write "Yes" or if they dont intersect write "No" .
Forexample line1 start (-2,2) and end (2,2) line2 start (-3,-2) and end (2,3)
- The lines are intersect. We will write "Yes".
- Input : -2 2 2 2 -3 -2 2 3
Output : "Yes"
- I need this problem's solution . Thanks.
Auto comment: topic has been updated by nemesis (previous revision, new revision, compare).
I think there are formulas which can help you.
The top answer in this link helps me evertime:
http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect
This tells you where they collide, which is more information than you need. If you want a simpler one, there is a simpler approach with only 4 cross products.
Consider two segments — (A,B) and (C,D). Let S(P1,P2,P3) be the oriented area of triangle (P1,P2,P3). It's easy to see that if the segments intersect, then A and B should be in different half-planes about line (C,D) and C and D should be in different half-planes about line (A,B) (I am not sure if "about" is the right word, I am sorry if I am wrong and I guess I am). So we want S(A,B,C)*S(A,B,D)<0 and S(C,D,A)*S(C,D,B)<0, of course it may be <=0 depending on what you call intersection :)
Thanks ...