Сеть дорог

В задаче требовалось построить граф, в котором будет не слишком много вершин, и запустить на нем алгоритм поиска кратчайшего пути. А также, аккуратно разобрать крайние случаи, когда ответа не существует.

В первых группах можно было строить граф, содержащий O(k2) вершин. А именно, сделаем вершинами все целые точки с координатами по модулю не превышающими k. Ребра нужно провести между точками, являющимися соседними в каком-нибудь квадрате, а так же, между концами отрезков радиальных дорог. Несложно показать, что каждая радиальная дорога содержит ровно две целые точки — свои концы. Поэтому, построенный граф является корректным. Затем, запустим алгоритм Дейкстры, и найдем кратчайшее расстояние от начальной точки до конечной. В зависимости от реализации алгоритма, решение может работать за O(k4) или за .

Чтобы реализовать решение оптимальнее, нужно заметить несколько фактов. Оставим в рассмотрении только те квадраты, на которых лежит конец отрезка или точка. В каждом квадрате рассмотрим все точки, которые есть во входном файле, и углы квадрата. Расположим их в порядке обхода, и проведем ребра между соседними. Затем, проведем ребра, соответствующие отрезкам. В итоге, получится граф с O(n) вершин и O(n) ребер. На нем требуется запустить алгоритм Дейкстры. Итоговая асимптотика