S
Посчитать принадлежность оболочке. Потом посчитать принадлежность "исключению контура и выпуклой оболочки"(эти многоугольники)
Size: a a a
2020 November 19
S
Я же не говорил, что это сразу приведёт к решению как-никак)
CD
Посчитать принадлежность оболочке. Потом посчитать принадлежность "исключению контура и выпуклой оболочки"(эти многоугольники)
итого n^2 * log n правильно понимаю?
K
Не проще за n*m?
CD
Не проще за n*m?
для этого надо открыть теорию
K
Проводим из проверяемой точки луч, не проходящий через вершины контура, считаем число пересечений с отрезками
K
Четное - снаружи, нечетное - внутри, отдельно проверить, не на отрезке ли
K
По ограничениям норм
CD
Проводим из проверяемой точки луч, не проходящий через вершины контура, считаем число пересечений с отрезками
да посуммируй углы по контуру, что с тобой не так :)
RR
Построить выпуклую оболочку. Сравнить с изначальным контуром. Найти исключение из оболочки и контура. Проверять точку в этих треугольниках.
И это всё вместо 10 строчек кода?
K
да посуммируй углы по контуру, что с тобой не так :)
Потери точности
CD
Потери точности
там 0 или 2*pi
K
Хотя на таких ограничениях норм
CD
уж с такой точностью справимся, правда?)
K
Непонятно, вроде обои решения одинаково хорошо пишутся
CD
Непонятно, вроде обои решения одинаково хорошо пишутся
да не, в одном из них многовато ифов
S
итого n^2 * log n правильно понимаю?
а не просто n*m?
CD
а не просто n*m?
построить пример где выпуклая оболочка каждый раз содержит 5 точек?
S
построить пример где выпуклая оболочка каждый раз содержит 5 точек?
Не понимаю о чём ты, потому да.
CD
Не понимаю о чём ты, потому да.
Ну разница между невыпуклым N-угольником и его выпуклой оболочкой может быть невыпуклый N-3 угольник