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

A geometry problem
Автор sieunhanbom04, история, 8 лет назад, По-английски

Given 2 sets of point namely P={p1,p2,...,pn} and Q={q1,q2,...,qn}. Those 2n points all lie on the unit circle. Draw segment (pi,qi). Determine the number of intersecting pair of segments. The required complexity for this problem are O(nlogn^2) and O(nlogn). Could someone give me a hand in this problem?

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

»
8 лет назад, # |
← Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

I'm supposing all the points are distinct. After ordering all the points, it is possible to map each point to an integer in the range [1, 2N] based on its position. After that, each line segment can be seen as a segment [Li, Ri]. Now, for each segment [Li, Ri], you need to count how many segments [Xj, Yj] are there such that Xj < Li < Yj < Ri; i.e., the segments intersect. This can be done with line sweep + fenwick tree (for each starting point Li in the line sweep you count how many "active" ending points Yj are smaller than Ri). Some care must be taken with the cyclic segments but I think this should be easy.

By the way, can you provide the problem link, please?

→ Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Not exactly this problem, but similar problem here. I think in this problem we have to find count of intersecting pairs, then answer is ((cnt_intersecting_pairs) + n + 1). If I'm wrong, please correct me.

    Some solvers of this problem told it is solved by fenwick tree as you mentioned.

    → Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It is just an problem in my "algorithm design and analysis" course so I do not have link for this problem. By the way, we share the same thought on this problem, however, the cyclic segments appear really hard to handle, not that easy.

    → Ответить