Задача D. Дом у дороги

Первоисточник: Всероссийская олимпиада школьников по информатике 2010/2011 учебного года. Региональный этап, первый тур, 21 января 2011 г.

URL первоисточника: http://neerc.ifmo.ru/school/archive/2010-2011/ru-olymp-regional-2011-archive.rar

Задачу добавил: alef

Успешно сдано решений: 1

Ограничение по времени: 4 с
Ограничение по памяти 256 Мб

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

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

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

Формат входного файла input.txt

Первая строка входного файла содержит одно целое число n — количество наиболее важных трасс (1 ≤ n ≤ 10⁴).
Последующие n строк описывают трассы. Каждая трасса описывается четырьмя целыми числами x₁, y₁, x₂ и y₂ и представляет собой прямую, проходящую через точки (x₁, y₁) и (x₂, y₂). Координаты заданных точек не превышают по модулю 10⁴. Точки (x₁, y₁) и (x₂, y₂) ни для какой прямой не совпадают.

Формат выходного файла output.txt

Выходной файл должен содержать два разделенных пробелом вещественных числа: координаты точки, в которой следует построить офис министерства дорожного транспорта. Координаты по модулю не должны превышать 10⁹, гарантируется, что хотя бы один такой ответ существует. Если оптимальных ответов несколько, необходимо вывести любой из них.
Ответ должен иметь абсолютную или относительную погрешность не более 10^-6, что означает следующее. Пусть максимальное расстояние от выведенной точки до некоторой трассы равно x, а в правильном ответе оно равно y. Ответ будет засчитан, если значение выражения |x – y| / max{1, | y| } не превышает 10^-6.

Пример входного файла

     4

     0 0 0 1

     0 0 1 0

     1 1 2 1

     1 1 1 2

Пример выходного файла

     0.5 0.5

Примечание

Правильные решения для тестов, в которых n ≤ 100 и все прямые параллельны, оцениваются из 20 баллов.

Правильные решения для тестов, в которых n ≤ 100 и все прямые параллельны осям координат, оцениваются из 20 баллов.

Правильные решения для тестов, в которых n ≤ 100, оцениваются из 70 баллов (в эти баллы включаются также по 20 баллов за случаи, описанные в предыдущих двух абзацах).

Сдать задачу

Задать вопрос жюри по этой задаче