Shot through vertical segments

Revision en2, by tom, 2015-10-19 17:15:30

Hello everybody,

Here's the problem: We have n < 100, 000 vertical segments with different x-coordinates. Is there any line that goes through each of it?

I've already known solution: We have to find 2 convex hulls: lower hull of upper points and upper hull of lower points and check if they intersect.

I'm getting WA on this problem. I know how to find convex hull, but I'm not sure to idea of checking intersection. Could you provide me how you would that?

Thanks

Tags geometry, convex hull

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English tom 2015-10-19 17:15:30 32
en1 English tom 2015-10-19 17:06:39 478 Initial revision (published)