На сайте acmp.ru появились 300 новых задач, и сейчас самое время их решить.
Это четвёртая задача регионального этапа Всероссийской олимпиады школьников по информатике 2010 года, то есть последняя в первом туре, поэтому уровень сложности выше среднего.
Задача на геометрию, а работа с нецелыми числами, множеством формул и разбором разных частных случаев всегда доставляют трудности.
Давайте посмотрим, как можно облегчить страдания. Во-первых, чтобы не натолкнуться на проблемы с накопившимися округлениями при работе с вещественными числами, рекомендую использовать класс рациональных чисел Rational, о котором писал ранее. К счастью, в этой задаче большая часть действий будет по пересечению прямых, построению перпендикуляров и т.д., для чего подходят арифметические операции.
Во-вторых, можно использовать приём, который довольно часто работает в задачах на геометрию: ответом (или его частью) является какая-то точка пересечения. И остаётся только понять что и с чем пересекать, найти все такие точки и перебрать их в качестве ответа. Давайте этим и займёмся.
В задаче говорится о точках и окружности, это должно наводить на мысли об описанной окружности. И правда, если бы было три точки, а не четыре, то в качестве ответа подходила бы описанная окружность треугольника (если точки не лежат на одной прямой), тогда бы расстояние до всех было равно 0. Однако в задаче надо минимизировать радиус, но и это не проблема. Оказывается, что будет подходить любая окружность с центром в этой точке, в том числе и с нулевым радиусом.
Центр описанной окружности лежит в точке пересечения срединных перпендикуляров, поэтому давайте найдём все срединные перпендикуляры (6 штук), все точки их пересечения (15 штук) и проверим каждую из них, может ли она быть центром искомой окружности. Только надо учесть совпадающие точки пересечения и совпадающие или параллельные перпендикуляры.
Чтобы проверить подходит точка в качестве центра искомой окружности или нет, достаточно найти расстояния от неё до заданных достопримечательностей. Если все они будут равны, то значит ситуация подобна рисунку, только с четырьмя точками, и мы можем построить бесконечное число окружностей. Если различных расстояния два, тогда мы можем построить ровно одну окружность с центром в этой точке и радиусом, равным среднему арифметическому (тогда достопримечательности с меньшим расстоянием окажутся внутри окружности, а с большим - снаружи). Если три или все четыре точки имеют различные расстояния до точки, то никакую окружность построить не получится.
Давайте посмотрим на реализацию данного решения. Для удобства заведём несколько полезных структур. Например для точки на плоскости:
Мне не очень нравится создавать такую структуру, потому что точка на плоскости эквивалентна вектору из центра координат. А для вектора определены различные операции, которые для точки выглядят не естественно (например, здесь это операция деления на число, но нам нужна для удобного вычисления середины отрезка).
К тому же структуру Vector всё равно приходится делать, потому что конструктор точки по двум точкам и косое произведение точек - это что-то совсем странное.
И для полного комплекта заведём Circle для хранения ответа и Line для срединных перпендикуляров:
Стоит отметить, что именно в использовании структуры Line проявляется преимущество в наглядности от создания двух структур Point и Vector.
Напишем три функции, которые выполняют геометрические операции: нахождение срединного перпендикуляра, квадрата расстояния между двумя точками (чтобы лишний раз не вычислять квадратный корень) и точки пересечения двух прямых (при условии, что она есть).
Для сокращения кода введём вспомогательную структуру (чтобы не писать pair<Line, pair<int,int>> и a.second.second) и переопределим тип данных.
Теперь можно перейти к самому решению. Сначала считываем данные и для каждой пары точек находим срединный перпендикуляр, складываем их (и индексы точек, которым они соответствуют) в вектор.
Проинициализируем ответ:
inf - флаг, того, что окружностей бесконечно много,
result - подходящая окружность минимального радиуса,
centers - все центры подходящих окружностей (чтобы знать их количество и не переживать о совпадающих точках пересечения).
Осталось перебрать все пары найденных перпендикуляров:
И рассмотреть два случая. Если прямые совпадают, значит достопримечательности образуют равнобедренную трапецию и все точки лежат на одной окружности, либо они лежат на одной прямой и окружность минимального радиуса как раз в точке основания срединного перпендикуляра.
В первом случае центр окружности можно найти, если взять ещё какой-нибудь срединный перпендикуляр (он уже точно не будет параллелен, так как точки не на одной прямой) и найти пересечение с ним, а радиус будет равен 0. А во втором случае - это просто середина отрезка AB. В обоих случаях количество окружностей бесконечно, поэтому сразу выставляем флаг inf.
Если перпендикуляры не совпадают, убедимся, что они пересекаются, найдём точку пересечения и посчитаем расстояния от неё до всех достопримечательностей. После этого посмотрим, сколько получилось различных чисел и сделаем соответствующие выводы.
Осталось лишь вывести ответ.
Код получился большой, но и задача не самая лёгкая. Если код непонятен, то спрашивайте в комментариях.
Предыдущий выпуск: Задача 21. Зарплата
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.