| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | jiangly | 3670 |
| 3 | Kevin114514 | 3657 |
| 4 | maroonrk | 3355 |
| 5 | Um_nik | 3353 |
| 6 | squareOf105 | 3346 |
| 7 | tourist | 3343 |
| 8 | strapple | 3324 |
| 9 | heuristica | 3322 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | AmShZ | 143 |
| 5 | Um_nik | 141 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 133 |
| 8 | maroonrk | 133 |
| 10 | qwexd | 129 |
could someone please help me with this problem? given n circles (n <= 500000), count the number of circles that have a common point. it's guaranteed that the circles don't overlap.
here's the complete statement: http://coj.uci.cu/24h/problem.xhtml?pid=4161〈=es
thanks in advance
I believe you can do a sweep line, maintaining circles intersecting your current line, sorted by center coordinate. When a new circle appears, just check if it has common points with the neighbors.
Consider this case (sweeping rightward)
4
0 3 3
0 -3 3
3 0 1
-3 0 1
Proof sketch for correctness: If two circles touch, when the sweep line goes through the point of contact, the two circles will be adjacent in the list. Thus, it suffices to only consider all pairs of circles that are adjacent in the list at some point in time.
thank you very much!
thank you very much!