5udipta's blog

Need Help
By 5udipta, 10 years ago, In English

I need help for this problem. Please.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Bruteforce all n points and consider as a "center". There is one straight stripe(lane) with 2 km width and infinite length. Consider all the sptripes with central point on it's edge. For each non central point you should create two events: anlge of a stripe when city enter and leaves the stripe. Sort them by angle. Now you can count how many points lies on each of the stripes in O(n). Total complexity will be O(n^2 * log(n)).

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks for your reply. It becomes hard to me to implement your idea. It will be helpful if you kindly explain your idea that is easy to understand for me.

    Sorry for my bad English.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Red point is a center. Blue points — other cities. Rotate stripe around it.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        There are two pictures: on the first one rightmost point enters in to stripe, on the second one leaves stripe. When you rotate the stripe near 180 degrees, there will one more enter event, and one more leave event (stripe will be upper than red point). Calculate all 4 events for each point, sort them by angle...

        → Reply