Given N circles (N <= 100000) with radius <= 10 on 2d plane (-20000 <= X,Y <= 20000) I have no idea how to solve it, can someone help me T^T.
edit: count number of pairs of intersections. ps. sorry for my bad english.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
7 | cnnfls_csy | 3569 |
9 | ecnerwala | 3494 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 158 |
4 | awoo | 158 |
4 | cry | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 152 |
10 | maroonrk | 151 |
Given N circles (N <= 100000) with radius <= 10 on 2d plane (-20000 <= X,Y <= 20000) I have no idea how to solve it, can someone help me T^T.
edit: count number of pairs of intersections. ps. sorry for my bad english.
Name |
---|
Provide the problem source. So many people ask about problems from ongoing contests and tests...
Obvious hint: exploit a low constraint for radius.
sorry, the problem is from this website (Thai language)
https://beta.programming.in.th/tasks/1054
This is my source code.
https://pastebin.com/ykc73Mv0
above solution is passed all test case but I think there are some case that my code doesn't work (ex. all circle are on the same X so it well be O(n^2))
For a circle centered at $$$(x, y)$$$, you need to iterate over $$$x_2$$$ in $$$[x-20, x+20]$$$ and $$$y_2$$$ in $$$[y-20, y+20]$$$ and then check if there's any circle centered at $$$(x_2, y_2)$$$ (use a map or unordered map). The complexity should be $$$O(N \cdot R^2)$$$, maybe multiplied by logarithm.
thanks, I'll try to implement this.