Опубликован первый саратовский контест на Петрозаводских сборах. Это было в далеком 2002-ом году, тогда сборы проходили на природе, на берегу Урозеро. Именно на тех сборах наша команда познакомилась с Андреем Лопатиным, Олегом Христенко и большим и дружным коллективом из Петрозаводска: Кузнецовым В.А., Петровичем, Романом Сошкиным. Короче, сборы были замечательные, а мы заняли там первое место.
К сожалению, у меня не осталось результатов того контеста (с минутами сдачи задач), так что призраков в этом контесте нет. Если у кого есть результаты — делитесь.
Task H. Круги
В первом примере странный вывод: сказано выводить 2 числа, а тут 1. Во втором примере выводят 0 0, хотя у кругов есть касание. А по условию "имеют хотя бы одну общую точку"
может кто-нибудь пояснить что тут все-таки нужно найти: пересечение кругов или окружностей?
Не смотри вообще на примеры в этой задаче. Пересечение действительно кругов, а не окружностей. В обоих тестах вроде как ответ "1 2" получается.
спасибо.
кто-нибудь знает решение быстрее, чем n^2?
Как правильно решать С (ну, или в чем подвох 5 теста)?
Во-первых, проверим, что отрезок из начальной точки в конечную пересекается хотя бы с одной стороной многоугольника, иначе ответ — расстояние между этими точками. Дальше несколько способов.
1 вариант (который я писал):
Ответ всегда имеет следующий вид: сначала нитка идет из начальной точки в какую-то вершину многоугольника, дальше движется по его границе до некоторой вершины, а потом идет до конечной точки. Найдем кандидатов на вершину, в которую нитка пойдет из начальной точки (это будут те вершины, для которых отрезок с концами в этой вершине и начальной точке не пересекает ни одной стороны многоугольника). Аналогично определим кандидатов для конечной вершины. Дальше просто переберем все возможные пары первой и последней вершины на многоугольнике, выберем из всех вариантов лучший.
2 вариант (не писал):
Построим выпуклую оболочку на множестве вершин многоугольника, начальной и конечной точке. Оптимальный путь будет полностью лежать на выпуклой оболочке. Найдем минимальное расстояние между нужными точками по выпуклой оболочке.
Почти также как описали выше, но без разбора типа пути, а просто поиск кратчайшего пути в графе.
По задаче H авторское решение предполагало квадратичное решение? просто сложно оценить сейчас, на сколько много было 10000 ^2 во время тех сборов в 2002 году.
Наверное, просто n^2 не заходило, но есть очень простой оптимайз, который добавляет коэффициент 1/9, и с которым должно заходить спокойно (не зря ведь там стоят такие маленькие ограничения на х, у).
Опиши пожалуйста оптимайз
У нас 1 <= x, y <= 100. Сделаем массив 100 на 100, и будем хранить в каждом его элементе "есть ли в точке (x, y) окружность". При обработке очередной окружности (поскольку радиус каждой окружности >= 1), проверим данную точку и 8 соседних на наличие окружности там (если есть хотя бы один круг, то они пересеклись). Это работает за О(n) и не влияет на асимптотику. Если ни одна проверка не завершилась успехом, то можно утверждать, что n <= 102*102/9, а значит, n^2 приблизительно 10^6 (оптимайз даже а 81 раз, перепутал).