@Taras_Z

Есть массив точек, заданных координатами х и y.
Нужно найти три ближайшие точки к данной, чтобы данная точка была в треугольнике, вершинами которого являются искомые точки.
Меня интересует самый быстрый алгоритм.

0

@salam

люди, вы когда задачи придумываете, придумывайте их решаемыми... как я должен понять фразу "в треугольнике"? если данная точка лежит на одной из сторон? может ли треугольник вырождаться в прямую?...

0

@Taras_Z

salam, точка также может лежать на стороне треугольника. Вершины треугольника - три искомые точки.

0

@AndrSlav

На вскидку:
Вычислить длины векторов из точки к точкам массива, а потом добавлять в выборку по очереди точки, соответствующие минимальным длинам векторов и сортировать их по описывающему контуру вместе с заданной точкой. Когда заданная точка не будет попадать в выборку- она внутри и последняя добавленная точка с соседними в выборке образуют искомый треугольник.

0

@Taras_Z

AndrSlav, Как по мне это не самый быстрый алгоритм. У меня сделано все так же, но это работает очень долго и поэтому мне надо быстрый способ.

0

@IrineK

Есть такая мысль:

Если воспользоваться, то массив из 200 точек, перебранных по три by brute force, "сдается" менее чем за секунду.

Миниатюры

 

0

@IrineK

А это - уже для 2000 точек.
Время выполнения: чуть больше 2 минут.

При этом, поскольку вы разрешили точке находиться на стороне, она приютилась в вершине треугольника )

Миниатюры

 

0

@Taras_Z

IrineK, Оно то так, но я делаю олимпиадную задачу, где надо уложиться в определенный тайм-лимит. В задаче, кроме этого алгоритма есть еще куча других, и вместе они будут выполняться достаточно долго. Мне просто нужно усовершенствовать это место.
Две минуты это очень долго. И точка может находиться на стороне, но не на вершине. Извиняюсь, что не указал этого раньше.

0

@salam

Тогда бы уж дали ссылку на задачу.

0

@Taras_Z

salam, Ссылку дать не могу, так как такой не существует.
Могу объяснить суть задачи.
В комнате есть большой круглый (синий ) сундук посреди комнаты.
Надо перенести сундук из комнаты - но мешают колонны ( оранжевые ) .
Нужно найти , через какую стену возможно вынести сундук ( левая, правая , верхняя , нижняя) . (Если это возможно).
Переносить сундук через угол нельзя.
В файле задается размер комнаты ( XY ) , координаты и диаметр сундука , количество колонн n , их координаты и диаметр.
Выводить 0 , если сундук вынести из комнаты нельзя , или указывать номер стены , через которую можно вынести ящик ( все варианты ) .
Если нижняя стена - 1
Верхняя - 2
Левая - 3
Правая - 4
Пример файла:

Ответ: 1

Миниатюры

 

0

@IrineK

Две минуты для 2000 "колонн".
Для тех 11, которые мы видим в примере - речь идет о долях миллисекунд.
Кстати, в корректно поставленной спортивной задаче должно быть дано ограничение на их кво.
Каковы границы этого числа?

0

@Taras_Z

IrineK, 11 колонн это лишь пример.
Четких ограничений на количество колонн сожалению нет. Не надо за меня решать всю задачу. Она уже решена. Я просто хочу улучшить время ее выполнения. То что мне нужно, сказано в моем первом сообщении. Если вы не знаете лучшего алгоритма, то не надо писать то, что здесь было уже написано.

0

@IrineK

Почему меня это должно останавливать? )

Все-таки хочется знать порядок величин, в частности заинтересовали ограничения на площадь комнаты: каждая стена длиной до сотен, до тысяч? Думаю, эдакий bitmap помещения может сильно помочь.

Т.е. не все тесты проходим. Тогда задача - не совсем решена

0

@Taras_Z

IrineK, У меня нет точных ограничений. Также я не знаю, проходит ли мое решение по времени, потому что не могу проверить его. Вы можете решать эту задачу. Даже, если хотите, можете мне рассказать свою идею ррешения задачи. Просто все, что я хочу сейчас это усовершенствовать свой ​​метод.

0

@IrineK

ОК.
Тогда сориентируйте во времени, которое необходимо вашему коду, чтобы перемолоть пример.
И какое время хотелось бы получить?

0

@Taras_Z

Чем меньше тем лучше)
Пример выполняется за 0,003 с.
Но при увеличении колонн время существенно изменится.

0

@IrineK

Основная идея альтернативного подхода такая.

Мне нужно пронести круглый сундук с определенным конечным радиусом, обходя круглые препятствия (fig1).

В принципе, если я "сброшу" радиус сундука на эти препятствия, то задача сводится к прохождению пикселя, который может проходить и по границе препятствий (fig2 - там пиксель несколько преувеличен).

Дальше - волновой алгоритм нам в помощь. Заходим со стен комнаты.

Однако, волнует следующее. Обе картинки даны с зумом 50. Видим два пути, похожих на выходы: слева и внизу.

В реале сундук проходит внизу впритык (окружности касаются, но не пересекаются). Слева по расчетам сундуку не хватает 0,015 пикселя, чтобы протиснуться. Но мы ставим на построение карты, а не на расчеты. Исходя из "0,015" зума 200 достаточно, чтобы увидеть, что окружности слева "наезжают", а не касаются (fig3 - слева, fig4 - внизу, зум 200).

В общем, Брезенхейм и "правильный" масштаб нам алсо в помощь )

Миниатюры

     

 

0

@Taras_Z

IrineK, Очень интересный метод!)
Спасибо)

0

@Taras_Z

Никто не знает лучшего алгоритма?

1

@uhx

Мде... классная задача. Тогда тайминг ничего не решает, ибо можно ввести максимальное число и тут даже самый оптимальный алгоритм не справится за секунду-другую.

0