I need help for this problem. Please.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 4 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | Dominater069 | 154 |
| 8 | nor | 154 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 14.11.2024 20:03:14 (k3).
Десктопная версия, переключиться на мобильную.
При поддержке
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)).
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.
Red point is a center. Blue points — other cities. Rotate stripe around 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...