Given 'n' circles (each defined by center and radius) Write an algorithm to detect if given circles intersect with any other circles in the same plane
Better than O(n^2) complexity
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 165 |
| 2 | 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
Время на сервере: 15.11.2024 11:56:31 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
If I got the problem correctly, for each circle you just need to loop though all others and compare the distance between two centers versus the sum of two radiuses. Two circles intersect if the former is not greater than the latter.
The time complexity for the above approach would be O(n^2) ______
Updated 1: Sorry the time complexity is not good enough
Yes, but a better approach O(NlogN) is reqd.
Sweep line, make a vertical line sweep from x=-inf to x=+inf, whenever it touch a circle from left insert the Y coordinates of its center to a
std::setand check if this circle intersects with the two circles which become immediately before and after this circle in thestd::set, whenever the line touches from a circle from right remove that circle from set now check if the two circles which was before and after the removed circle in thestd::setintersect with each other.UPD: I considered that intersecting of two circles means having a common area
Can u explain using some example.
A brief example would be very useful.Give me an example you want me to explain
Any example of choice where I can visualise the algo?
Maybe 4 circles like this Pic where
1 intersects 2, 3, 4
2 intersects 3, 4
3 intersects 4
or any other to get intuitive explanation.
if you have 4 circles such that all pairs intersect with each other then here's how the algorithm will work:
the sweeping line will move until it touches the first circle from the left, you will insert its Y coordinates to
std::setnow the line will continue sweeping until it touches another circle from left and you will add its Y coordinates tostd::set, since there was only one circle in thestd::setthe newly added circle will come either after or before it so you have to check if those two circles intersect and they indeed intersect because all circles intersect with each other so you just return that there's intersection and terminate the algorithm.This link may help you
Do I have to say whether there are 2 circles that intersect or the pairs of circles that intersect?