Блог пользователя tom

Автор tom, история, 9 лет назад, По-английски

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

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится