Дано $%n$% точек на плоскости. Предложите как можно более быструю процедуру нахождения круга минимального радиуса с центром в начале координат, содержащего не менее половины точек. (Считаем, что арифметические операции и сравнения выполняются за единицу времени)

задан 8 Мар '16 19:46

10|600 символов нужно символов осталось
1

Считаете расстояния до "половины точек $%+1$%" и по ходу выбираете максимум... Эта "большая половина" будет содержаться в круге... вторая уже не важна по условию...
В этом варианте $%([n/2]+1)\cdot 4$% операций...

=======================

Вариант 2
Найти максимум по первой и второй координатам у половины точек... и взять окружность радиуса $%R^2=x_{\max}^2+y_{\max}^2$%...
Тут вроде $%([n/2]+1)\cdot 2$% операций получается...

ссылка

отвечен 8 Мар '16 20:58

изменен 8 Мар '16 22:19

@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
10|600 символов нужно символов осталось
2

Если в лоб, то вычисляете расстояние от каждой точки до начала координат (точнее квадраты расстояний). А затем находите медиану данного множества. Вот что по поводу этого алгоритма советует википедия. Можно ли улучшить? Можно!

ссылка

отвечен 8 Мар '16 20:06

изменен 8 Мар '16 20:10

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×281
×197

задан
8 Мар '16 19:46

показан
1105 раз

обновлен
9 Мар '16 1:02

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru