Ближайшая точка, типа прикладная Опции Рейтинг

[alan]

Представьте, что у вас есть множество А из M точек на плоскости (x_i,y_i). Есть информация о них - по две координаты.

Потом нам дают еще одну точку - B(b_x,b_y). Нужно найти:
а) Точку из множества А ближайшую к B.
б) N ближайших точек к B.
в) Все точки на растоянии меньше чем R от B

Задача - оптимально организовать информацию о точках А. Оптимальность определяется средней скоростью выполнения а), б) или в).

[alan]

Для примера очевидное и далекое от оптимальности решение:


I)
1. Организация. Точки в произвольном порядке записываем в масив.
2. Поиск. Перебираем весь масив от первого элемента до последнего. И для каждого элемента считаем расстояние до точки B, по формуле sqrt((b_x-x_i)^2+(b_y-y_i)^2). Из растояний выбираем минимальное(б) N минимальных, в) меньшие, чем R). Находим точку, которой соотвествует это расстояние.

Сколько платишь?

А как платить? За что? За решение + доказательство оптимальности? Не думаю что такое существует.
Поэтому и передумал в соответствующем разделе писать.
Хотя хорошо было бы иметь раздел в котором каждый мог бы делиться, "тем, что его беспокоит"

[idler_]

А как платить? За что? За решение + доказательство оптимальности? Не думаю что такое существует.

Платить деньгами)
За то, что тебе нужно.
Смотри: тебя интересует решение какой-то задачи, то есть решение идёт тебе на пользу.
Вряд ли кого-то ещё это интересует)
Какого-то особого логического интереса задача не вызывает.
Зачем тратить время просто так? )

[JK]

Зачем тратить время просто так? )

Человек с таким ником не может задавать таких вопросов :-)
Но возможно, если человек тратит время "просто так" ему доставляет это удовольствие, или он хочет помочь, или он не тратит время на раздумья над вопросом "Зачем тратить время просто так? "