Решение задач Petr Mitrichev Contest 1

[AndreySUrSU]

если кто-то знает решения каких-то задач с этого контеста, интересно было бы пообсуждать.
мы сегодня решали. сдали, правда, всего три. но на другие есть задумки, кот пока не доведены до конца.
когда-нибудь наверное займемся дорешиванием.
хотелось бы пообсуждать.

[AndreySUrSU]

в данный момент меня больше всего интересует задача с про гиперболоид. почему-то наше решение не принялось.
мы строили ломаную ну и считали длину ломаной.
вроде все было нормально.
кто как решал?

[artie]

нужно построить сетку на гиперболоиде и найти кратчайший путь, например, алгоритмом дейкстры

[AndreySUrSU]

ну а с какой точностью сетку строить?
на сетке расстояние - просто отрезок?

[artie]

с такой точностью, чтобы прошло по точности и по времени.
ребра надо строить так, чтобы по ребру не улететь с верхнего края гиберболоида на нижний.

[Fever]

сетку надо строить с помощью квадратичного дерева.