Дано массив окружностей
окружность - координаты X,Y И R - радиус
и точка - координаты X,Y
Нужно определить в какую именно окружность попадает точка. Тоесть на выходе один индекс массива окружностей.
Если точка попадает сразу в 2 или больше окружностей то выбрать нужно ту центр которой ближе всего к точке.
Задачу можно решить простым проходом по массиву. O(n)
Можно ли как то оптимальнее организовать поиск?
Разрешено изменять структуры данных, сортировать итд.
Примечание:
Задача Offline - окружности в базе хранятся, а вот точка будет каждый раз новая. Вот точка часто будет менятся
Примечание:
точки сразу не известны а возникают по мере работы программы
Примечание:
ок посмотрю, только где вы нашли в компе бескончность? :)
Примечание:
1st nearest neighbour search problem, там поиск в многомерном пространстве а у меня двумерное, как перейти от 2мерного к N мерному?
RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.
Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.
Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.