| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
Hi, I've solved this problem before with O(N^2 lgN) algorithm. For example: http://pastie.org/3129354
But today I got to this problem: http://www.spoj.pl/problems/CHASE/
I got TLE with O(N^2 lgN) algorithm, and a O(N^2) algorithm is mentioned in comments, could someone explain how it works.
N means the number of points given.
Maybe by O(N^2)-solution a hash-map solution was meant?
If you fix one point, you have to find maximum number of another points that have the same polar angle. So the problem transforms into finding the number that encountered maximum number of times among given N-1 double numbers - this can be done with hash-map (also you can try to replace double angles with pairs of integers - reduced fractions).