Темы --> Информатика --> Алгоритмы --> Алгоритмы поиска --> Тернарный поиск
---> 2 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников
    Муниципальный этап(80 задач)
    Окружная олимпиада(18 задач)
    Региональный этап(109 задач)
    Заключительный этап(97 задач)
Страница: 1 Отображать по:
#3209
Дом у дороги
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
Пересечение полуплоскостей за O(NlogN)

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

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

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

Входные данные

Первая строка входного файла содержит одно целое число \(n\) — количество наиболее важных трасс (\(1 \le n \le 10^4\)).

Последующие \(n\) строк описывают трассы. Каждая трасса описывается четырьмя целыми числами \(x_1\), \(y_1\), \(x_2\) и \(y_2\) и представляет собой прямую, проходящую через точки \((x_1, y_1)\) и \((x_2, y_2)\). Координаты заданных точек не превышают по модулю \(10^4\). Точки \((x_1, y_1)\) и \((x_2, y_2)\) ни для какой прямой не совпадают.

Выходные данные

Выходной файл должен содержать два разделенных пробелом вещественных числа: координаты точки, в которой следует построить офис министерства дорожного транспорта. Координаты по модулю не должны превышать \(10^9\), гарантируется, что хотя бы один такой ответ существует. Если оптимальных ответов несколько, необходимо выведите любой из них.

Ответ должен иметь абсолютную или относительную погрешность не более \(10^{-6}\), что означает следующее. Пусть максимальное расстояние от выведенной точки до некоторой трассы равно \(x\), а в правильном ответе оно равно \(y\). Ответ будет засчитан, если значение выражения \(|x - y| / max(1, |y|)\) не превышает \(10^{-6}\).

Примечание

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

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

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

Примеры
Входные данные
4
0 0 0 1
0 0 1 0
1 1 2 1
1 1 1 2
Выходные данные
0.5000000004656613 0.4999999995343387
Входные данные
7
376 -9811 376 -4207
6930 -3493 6930 -8337
1963 -251 1963 -5008
-1055 9990 -684 9990
3775 -348 3775 1336
7706 -2550 7706 -8412
-9589 8339 -4875 8339
Выходные данные
4040.9996151750674 12003.999615175067
#3398
Велогонка
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Велосипедисты, участвующие в шоссейной гонке, в некоторый момент времени, который называется начальным, оказались в точках, удалённых от места старта на \(x_1\), \(x_2\), ..., \(x_n\) метров (\(n\) – общее количество велосипедистов). Каждый велосипедист двигается со своей постоянной скоростью \(v_1\), \(v_2\), ..., \(v_n\) метров в секунду. Все велосипедисты двигаются в одну и ту же сторону.

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

Требуется написать программу, которая по заданному количеству велосипедистов \(n\), заданным начальным положениям велосипедистов \(x_1\), \(x_2\), ..., \(x_n\) и их скоростям \(v_1\), \(v_2\), ..., \(v_n\), вычислит момент времени \(t\), в который расстояние \(l\) между лидирующим и замыкающим велосипедистом будет минимальным.

Входные данные

Первая строка входного файла содержит целое число \(n\) – количество велосипедистов.

В последующих n строках указаны по два целых числа: \(x_i\) – расстояние от старта до \(i\)-го велосипедиста в начальный момент времени (\(0 \leq x_i \leq 10^7\)) и \(v_i\) – его скорость (\(0 \leq v_i \leq 10^7\)).

Выходные данные

В выходной файл необходимо вывести два вещественных числа: \(t\) – время в секундах, прошедшее от начального момента времени до момента, когда расстояние в метрах между лидером и замыкающим будет минимальным, \(l\) – искомое расстояние.

Числа t и l должны иметь абсолютную или относительную погрешность не более \(10^{–6}\), что означает следующее. Пусть выведенное число равно \(x\), а в правильном ответе оно равно \(y\). Ответ будет считаться правильным, если значение выражения \(|x – y| / max(1, |y|)\) не превышает \(10^{–6}\).

Подзадачи и система оценки

Данная задача содержит четыре подзадачи. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.

Подзадача 1 (20 баллов)

\(2 \leq n \leq 50\), \(0 \leq  x_i \leq 1000\), \(0 \leq v_i \leq 1000\). Гарантируется, что существует ответ, в котором \(t\) – целое число, не превышающее 1000.

Подзадача 2 (20 баллов)

\(2 \leq n \leq 200\).

Подзадача 3 (30 баллов)

\(2 \leq n \leq 2000\)

Подзадача 4 (30 баллов)

\(2 \leq n \leq 10^5\)

Примеры
Входные данные
3
0 40
30 10
40 30
Выходные данные
1 30
Входные данные
5
90 100
100 70
100 70
110 60
120 35
Выходные данные
0.5 5.000000000000
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест