Банальная задача: Дано n точек на плоскости. Необходимо найти наибольшее количество точек, лежащих на одной прямой.
Вопрос: Решаема ли эта задача быстрее, чем за 
, или же О(n2) — с хеш-мэпом.
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/24/2024 07:26:55 (k2).
Desktop version, switch to mobile version.
Supported by
There is problem called 3SUM, for which there are no known subquadratic (o(n2)) algorithms in common case. Many geometric problems are proven to be 3SUM-Hard, including "Given n points, check if there are 3 collinear points". Some more information in this paper.