tom's blog

By tom, history, 5 years ago, In English

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

 
 
 
 
  • Vote: I like it
  • +9
  • Vote: I do not like it