№ | Пользователь | Рейтинг |
---|---|---|
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 | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
Название |
---|
pre-process the relation between central points and circles(inside/outside a circle) O(N2).
then answer the query in O(M), given 2 points, check which circles contain exactly 1 point outside the circle and 1 point inside the circle.
Total Complexity: O(N2 + QM) which is still ok for 2 sec
and total complexity O(NM+QM)
For each query (i, j), count the number of circles such that exactly one of control center i or control center j is inside the circle, and that's the answer.
https://codeforces.me/contest/33/submission/46096711
Why?
If both i and j are within a circle, there is no need to go over the fence. If they are both outside, there is no need. If exactly one of them is outside, they definitely need to go over that fence. O(MK)