Один алгоритм виден сразу (просто перебираем точки), но он жутко неоптимален, в худшем случае пар точек около
![$16\times10^36$ $16\times10^36$](https://dxdy-03.korotkov.co.uk/f/6/e/d/6ed9dd5226fc598ca7c1484ede3d3f4682.png)
.
Вчера не успел отреагировать: к сожалению, автор задачи зачем-то написал про линии сетки (а не просто про два направления), в результате чего создается впечатление, что робот может двигаться только по линиям сетки, из одного узла в другой узел. Но это не так, задача не дискретная, а непрерывная. Просто указаны два направления движения.
По-моему, дискретный вариант задачи был бы сложнее (потому что находить суммы и их асимптотику сложнее, чем интегралы).
-- Чт апр 23, 2020 11:54:28 --Если я правильно понимаю, решение заключается в "нарезании" многоугольника на трапециевидные (в общем случае) "ломтики", как если бы это был батон.
По крайней мере, мое понимание ровно такое же
![Smile :-)](./images/smilies/icon_smile.gif)
Увы, авторское решение недоступно, так что сравнить не с чем. У меня были подозрения, что есть какой-то "левый" способ, который менее затратен (какая-нибудь хитрая формула Грина, позволяющая бесплатно все свести к одномерным интегралам). А так да, дальше остается честный счет с единственным нюансом --- уложиться по времени.