Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

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

Need Help
Автор 5udipta, 10 лет назад, По-английски

I need help for this problem. Please.

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

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

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)).

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

    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.

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

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

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

        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...

        → Ответить