А если хочется наоборот — одну команду на несколько строк?
По моему все-таки в с++ и прочих джавах сделано лучше. Когда непечатаемые символы вроде переноса строки или табуляции (питон) влияют на логику программы с этим становится опаснее работать в обычных текстовых редакторах.
Хм, верно, можно и так понять
Однако это скорее баг русского или вообще языка. В математике "различных" означает именно "не одинаковых", а не более разговорное "всяких"
Трихроматное строение человеческого глаза достаточно удобно для создания изображения (на видеокарте) — rgb+a хорошо стыкуется с трехмерными координатами мира xyz+w, позволяет использовать для обработки координат те же вычислительные блоки что и для обрабортки цвета, и получившиеся четыре координаты удобно работают с двоичной системой счисления.
Как бы это все выглядело будь человек тетрахроматом?
Но многоугольник от этого может перестать быть "хорошим" — в нем могут появиться самопересечения. А значит в конце можно остаться не с одним треугольником, а с рандомной кашей из намотаных вокруг точки вершин.
Ну вот представьте многоугольник в виде буквы М с соединением снизу. Удалив треугольник из двух нижних точек и одной верхней мы получим самопересечение.
Возможно в конце можно будет сделать какой то вывод. Но это надо бы доказать. И в любом случае получится больше чем O(N) из-за того что "если с треугольником не получилось — переходим к следующему". Насколько больше — тоже как-то нетривиально посчитать.
Вы должны доказать что это работает, а не "не могу придумать варианта".
Вон возьмите пример из правой верхней картинки статьи, только точка находится "между ног" а треугольник вы взяли из трех нижних точек. Точка в нем лежит, а в исходном многоугольнике — нет.
Если точки многоугольника и искомая точка целые числа то там надо просто математикой выкинуть все операции деления, это возможно, и считать в целых числах. Достаточно просто. Но алгоритм пересечения отрезка с лучом придется переписать. Превращаться в последовательности вертикальных и горизонтальных отрезков не надо.
В случае выпуклого многоугольника исходная задача становится супер простой — проверить что точка лежит с одной стороны от прямых созданных из всех отрезков (например слева от всех отрезков)
Однако в задаче очевидно подразумевается произвольный многоугольник, что и нарисовано на картинках В произвольном многоугольнике треугольник составленный из трех последовательной точки может ему не принадлежать полностью или частично.
Превратили O(N) задачу в O(N^3) потому что найти треугольник в многоугольнике это O(N^2) в худшем случае для простых алгоритмов. Есть сложные (сложнее чем определение точки в многоугольнике) которые побыстрее на больших многоугольниках но все равно получается больше чем O(N^2)
Можно. Проверка здесь будет только по одной из координат, а не результат какого-то вычисления (которое подвержено ошибкам)
Многоугольник обходится в одну сторону (по или против часовой стрелки). Вот для каждого отрезка одна из точек — начало, вторая — конец. Конец одного отрезка это начало другого
Второй вариант — считать точку с меньшим Х началом, с большим Х концом. Это будет лучше обрабатывать еще один особый случай (внутреннее касание вершины)
Я могу точно сказать что можно потому что такой алгоритм я писал и он работает в проде.
Откуда брать топливо чтобы догнать мусор двигающийся с относительными скоростями 2-3 км/с?
Откуда брать окислитель чтобы сжечь "все что может гореть"?
Откуда брать технологии чтобы все что угодно могло гореть в космосе на одноразовом двигателе выдавая достаточно удельного импульса для полета на луну?
Вы представляете размер "импульса" необходимый чтобы с низкой орбиты отправиться к луне? (больше 3 км/c) — испарить на атомы проще.
А топливо на это где брать?
А если хочется наоборот — одну команду на несколько строк?
По моему все-таки в с++ и прочих джавах сделано лучше. Когда непечатаемые символы вроде переноса строки или табуляции (питон) влияют на логику программы с этим становится опаснее работать в обычных текстовых редакторах.
Да.
auto p = a; -b;
auto p = a -b;
auto p = a; (b=5);
auto p = a(b=5);
Я не сишник, уверен сишники сейчас еще десяток примеров приведут.
Парочку примеров, от нового майкрософта (2014+)?
Хм, верно, можно и так понять
Однако это скорее баг русского или вообще языка. В математике "различных" означает именно "не одинаковых", а не более разговорное "всяких"
Я уже видел йогурты в литрово выглядящих бутылках содержащих 690 мл. 690 мл уже в принципе округляется до половины литра.
Трихроматное строение человеческого глаза достаточно удобно для создания изображения (на видеокарте) — rgb+a хорошо стыкуется с трехмерными координатами мира xyz+w, позволяет использовать для обработки координат те же вычислительные блоки что и для обрабортки цвета, и получившиеся четыре координаты удобно работают с двоичной системой счисления.
Как бы это все выглядело будь человек тетрахроматом?
Но многоугольник от этого может перестать быть "хорошим" — в нем могут появиться самопересечения. А значит в конце можно остаться не с одним треугольником, а с рандомной кашей из намотаных вокруг точки вершин.
Ну вот представьте многоугольник в виде буквы М с соединением снизу. Удалив треугольник из двух нижних точек и одной верхней мы получим самопересечение.
Возможно в конце можно будет сделать какой то вывод. Но это надо бы доказать. И в любом случае получится больше чем O(N) из-за того что "если с треугольником не получилось — переходим к следующему". Насколько больше — тоже как-то нетривиально посчитать.
есть еще Manufactoria 2022 — мне ок зашла, слегка похоже на классику Spacechem и иже с ними
Вы должны доказать что это работает, а не "не могу придумать варианта".
Вон возьмите пример из правой верхней картинки статьи, только точка находится "между ног" а треугольник вы взяли из трех нижних точек. Точка в нем лежит, а в исходном многоугольнике — нет.
В статье выпускаемый луч вертикальный поэтому правильно считать по Х а не по У
Если точки многоугольника и искомая точка целые числа то там надо просто математикой выкинуть все операции деления, это возможно, и считать в целых числах. Достаточно просто. Но алгоритм пересечения отрезка с лучом придется переписать. Превращаться в последовательности вертикальных и горизонтальных отрезков не надо.
В случае выпуклого многоугольника исходная задача становится супер простой — проверить что точка лежит с одной стороны от прямых созданных из всех отрезков (например слева от всех отрезков)
Однако в задаче очевидно подразумевается произвольный многоугольник, что и нарисовано на картинках В произвольном многоугольнике треугольник составленный из трех последовательной точки может ему не принадлежать полностью или частично.
Массив это не множество — массив уже имеет порядок. Массив точек однозначно задает многоугольник.
Для данного конкретного алгоритма самопересечение многоугольника не играет роли.
Превратили O(N) задачу в O(N^3) потому что найти треугольник в многоугольнике это O(N^2) в худшем случае для простых алгоритмов. Есть сложные (сложнее чем определение точки в многоугольнике) которые побыстрее на больших многоугольниках но все равно получается больше чем O(N^2)
То что точка является результатом вычислений это неважно. Важно чтобы она была учтена один раз, и в этом случае полуоткрытые отрезки работают.
Полигон это массив точек а не отрезков. В отрезки уже превращаем его мы в алгоритме, и мы можем это сделать аккуратно.
Ну и "второму варианту" на порядок пофиг, а он все равно лучше первого
Поэтому и "второй вариант".
Можно. Проверка здесь будет только по одной из координат, а не результат какого-то вычисления (которое подвержено ошибкам)
Многоугольник обходится в одну сторону (по или против часовой стрелки). Вот для каждого отрезка одна из точек — начало, вторая — конец. Конец одного отрезка это начало другого
Второй вариант — считать точку с меньшим Х началом, с большим Х концом. Это будет лучше обрабатывать еще один особый случай (внутреннее касание вершины)
Я могу точно сказать что можно потому что такой алгоритм я писал и он работает в проде.
Последний вопрос я не понял