Define the distance between two points i, j max(|xi, xj|, |yi — yj|). Given n points (xi, yi). Find a point (X, Y) so that the sum of distances from this point to n points is minimized. N <= 1e5 xi, yi <= 1e9
Thanks in advance.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3494 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3315 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 164 |
2 | Um_nik | 163 |
3 | cry | 161 |
4 | atcoder_official | 159 |
5 | awoo | 157 |
5 | adamant | 157 |
7 | -is-this-fft- | 156 |
8 | nor | 154 |
9 | TheScrasse | 153 |
9 | Dominater069 | 153 |
Minimize sum of distances.
Define the distance between two points i, j max(|xi, xj|, |yi — yj|). Given n points (xi, yi). Find a point (X, Y) so that the sum of distances from this point to n points is minimized. N <= 1e5 xi, yi <= 1e9
Thanks in advance.
Rev. | Язык | Кто | Когда | Δ | Комментарий | |
---|---|---|---|---|---|---|
en2 | Loserinlife | 2023-06-12 14:00:54 | 5 | Tiny change: 'nimized.\nN <= 1e5\nxi, yi <' -> 'nimized.\n\nN <= 1e5\n\nxi, yi <' | ||
en1 | Loserinlife | 2023-06-12 13:59:20 | 266 | Initial revision (published) |
Название |
---|