rav_pr, Я не уверен, но кажется к такому определению сложения точек на эллептической кривой пришли из диафантовых уравнений. Вот есть у вас уравнение и пара его решений. Вам хочется получить больше решений. И вот складывая вот так вы получаете какре-то другое решение. Если просто пересекать с прямой, то потом из этих 3 точек вы, как ни складывайте их, ничего нового не получите. А если результат сложения еще и отразить, то потом можно его с предыдущими точками складывать и получать что-то новое.
Потом выяснили, что на некоторых кривых можно просто одно и то же решение складывать само с собой таким образом и получить вообще все решения уравнения и оно закрепилось, ибо теперь кривая оказалась циклической группой - весьма полезным в математике объектом.
Так-то, сложение могли бы определить как угодно, надо только что бы результат тоже на кривой лежал. Но исторически вот этот способ оказался интересен его и закрепили.
Alex XYZ, Там алгоритм за линию практически (логарифм от точек пересечения с прямой, а их обычно не много). Куда уж быстрее. Ну только если у вас многоугольник не выпуклый, но это не ваш случай похоже.
Alex XYZ, алгоритм работает для любых наклонов прямых, там нигде горизонтальность не используется. Про + и - оффсеты не понял. Вы разрезаете фигуру на 2 части? Или пересекаете с несколькими прямоугольниками?
Если я правильно понял о чём идёт речь, то можно рассуждать следующим образом
Да, в таком смысле так.
Как-то сталкивался с задачей, где были циклы, но небольшие, компоненты сильной связности были не больше 10
Тут принципиальная разница, ибо какая бы у вас формула не была и каким бы не был граф, пока граф ациклический, у вас работает один и тот же алгоритм. Можно универсальный солвер написать, который принимает граф ифункцию. Он и называется ДП. Если же есть циклы, то там уже в зависимости от конкретной формулы и формы циклов будет свой уникальный алгоритм решения. Поэтому эти решения некороректно считать ДП.
art_gara55555, Почему у вас все кнопки обрабатываются в switch, а BUTTON_ID_CLOSE_SERVICE - отдельно в конце? Теперь этот кусок кода сработает по любому WM_COMMAND, даже если там не BN_CLICKED
. Вообще, в ациклическом графе циклов нет по определению. "ациклический" же, т.е. без циклов. Это опечатка же? Вы имели ввиду просто ориентированный граф?
pavlik 322, Потому что это высокоуровневое объяснения сути алгоритма. Для быстрой реализации вам надо поддерживать счетчики входящих ребер и очередь вершин, в которых A(v)=0. Подсчитайте входящие степени. Изначально кладите в очередь все корневые вершины (степень 0). Потом доставайте из очереди вершину, выводите ее в ответ, вычитайте 1 из счетчиков и кладите в очередь те вершины, где счетчики стали 0.
Если делать совсем наивно, то да, там получается еще два цикла.
pavlik 322, Приведите опять код, я запутался. У вас там выше был проход по узлам и потом проход по всем ребрам, а не только по ребрам, выходящим из текущей вершины. В этом ключевая разница. Вы каждое ребро обработаете для каждой вершины. Т.е. получается O(VE) = O(N^3). Если же обходить только ребра исходящие из заданной вершины, то каждое ребро обойдется только один раз.
Потом выяснили, что на некоторых кривых можно просто одно и то же решение складывать само с собой таким образом и получить вообще все решения уравнения и оно закрепилось, ибо теперь кривая оказалась циклической группой - весьма полезным в математике объектом.
Так-то, сложение могли бы определить как угодно, надо только что бы результат тоже на кривой лежал. Но исторически вот этот способ оказался интересен его и закрепили.