Hey! Does anybody know how to solve this? Given n segments, count how many pairs of segments have a common point. There are no 2 overlapping segments and the segments are can make any angle with the origin of the cartesian plane.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 162 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 151 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 25.04.2024 16:40:52 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
you can do this with a sweepline approach Bentley–Ottmann algorithm
But if number of crossings is big (quadratic, let's say) this algorithms is bad since it explicitly lists all of them and count them one by one. However, I am not sure if the original problem is solvable at all in something like O(n^1.999) or whatever.
well there are improved versions for example in $$$O(n^{\log_2(1+\sqrt{5})}) \approx O(n^{1.695})$$$ from Chazelle or in $$$O(n^{1.5} \log{n})$$$ from Mairson and Stolfi. Thats still slower than $$$O(n \log{n})$$$ but i don't know any better algorithms for this or any lower bounds for the counting problem...