|
Дано $%n$% точек на плоскости. Предложите как можно более быструю процедуру нахождения круга минимального радиуса с центром в начале координат, содержащего не менее половины точек. (Считаем, что арифметические операции и сравнения выполняются за единицу времени) задан 8 Мар '16 19:46 
Uchenitsa |
|
Считаете расстояния до "половины точек $%+1$%" и по ходу выбираете максимум... Эта "большая половина" будет содержаться в круге... вторая уже не важна по условию... ======================= Вариант 2 отвечен 8 Мар '16 20:58 
all_exist @all_exist: здесь ведь в условии говорится о круге минимального радиуса с данным свойством. Как я понял, Вы просто взяли круг, содержащий все точки. Но здесь нужно, грубо говоря, найти окружность, которая точки "делит пополам" по количеству -- половина внутри, половина вне.
(8 Мар '16 23:46)
falcao
@falcao, да, про минимальность радиуса я недосмотрел... всё думал про минимум операций... "делит пополам" по количеству - всё же не менее... хоть все...
(8 Мар '16 23:51)
all_exist
@all_exist: если взять все, то вне окажется 0 точек, а внутри все. А надо, чтобы и вне, и внутри было примерно по n/2. То есть это задача о нахождения "медианы" массива.
(9 Мар '16 0:06)
falcao
@falcao, но в условии не говорится про "медиану"... и про "примерно n/2" не сказано... Тут нужно уточнение условие от автора топика ...
(9 Мар '16 0:28)
all_exist
1
@all_exist: не нужно, потому что это прямо следует из условия. Оно сформулировано корректно. Допустим, n чётно. Для простоты также будем считать, что все расстояния до точек разные. Если я возьму круг минимального радиуса из условия, то он содержит не менее половины точек. Если окажется, что он содержит их больше половины, то его радиус становится возможно уменьшить. То есть в условии задана именно "медиана", если брать случай общего положения.
(9 Мар '16 1:02)
falcao
|
