---> 8 задач <---
Источники
    Личные олимпиады(925 задач)
    Командные олимпиады(684 задач)
Страница: 1 2 >> Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Дима недавно поступил на работу в НИИ Плоских Кривых. Как следует из названия этого научно- исследовательского института, он занимается различными исследованиями в области плоских кривых. Недавно Димин начальник Георгий столкнулся с весьма интересной кривой, которая, как выяснилось после некоторого исследования, известна под названием Архимедовой спирали. Архимедова спираль плоская кривая, изображающая траекторию точки M, которая равномерно движется вдоль луча OK с началом в O, в то время как сам луч OK равномерно вращается вокруг точки O (см. рисунок). Другими словами, расстояние до начала координат ρ = OM линейно зависит от угла поворота φ луча OK. При этом повороту луча OK на один и тот же угол соответствует одно и то же приращение расстояния ρ.

Движение точки M можно задать с помощью ряда параметров:

• начального угла поворота α луча OK (измеряется в градусах против часовой стрелки относительно положительного направления оси OX);

• угловой скорости вращения ω луча OK (измеряется в градусах за единицу времени);

• начального расстояния R от точки M до начала координат (точки O);

• скорости движения V точки M по лучу OK.

Если, задав эти параметры, не ограничить время движения точки M, то получится бесконечная кривая, исследовать которую достаточно трудно. Поэтому Дима решил ограничиться исследованием некоторой части этой кривой той, которая получается при движении точки M от нулевого момента времени до момента времени T. Задача, которую решает Дима состоит в поиске прямоугольника минимальной площади со сторонами, параллельными осям координат, в который ее можно вписать.

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

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

Входной файл содержит четыре целых числа: ω (1 ≤ ω ≤ 100), V (1 ≤ V ≤ 100), R (0 ≤ R ≤ 100) и T (1 ≤ T ≤ 1000). В этой задаче считается, что начальный угол поворота α равен нулю.

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

В первой строке выходного файла выведите два вещественных числа — координаты левого нижнего угла искомого прямоугольника, а во второй строке — координаты правого верхнего угла искомого прямоугольника.

Ответ будет считаться правильным, если значение каждой из координат будет отличаться от истинного значения не более чем на 10-5.

Примеры
Входные данные
60 10 0 18
Выходные данные
-150.3028434716 -165.2754877824
180.0000000000 135.3362037333
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

Паук и паучиха плывут по озеру на двух веточках. Плавать они не умеют, поэтому смогут встретиться только тогда, когда веточки соприкоснутся.

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

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

Входной файл содержит 12 чисел: $x_1$, $y_1$, $x_2$, $y_2$, $x_3$, $y_3$, $x_4$, $y_4$, $v_{1x}$, $v_{1y}$, $v_{2x}$, $v_{2y}$. Координаты вершин первого отрезка: ($x_1$, $y_1$) и ($x_2$, $y_2$), координаты вершин второго отрезка: ($x_3$, $y_3$) и ($x_4$, $y_4$), скорость первого отрезка ($v_{1x}$, $v_{1y}$), скорость второго отрезка ($v_{2x}$, $v_{2y}$). Все числа целые и не превосходят по модулю $10^4$. В начальный момент времени веточки не соприкасаются. Гарантируется, что веточки имеют ненулевую длину.

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

Выведите в выходной файл время до ближайшего момента, когда веточки соприкоснутся, с ошибкой не более $10^{-4}$. Если веточки не соприкоснутся никогда, выведите число -1.

Примеры
Входные данные
0 0 -1 3
4 4 7 7
3 0
0 -1
Выходные данные
1.6
Входные данные
0 0 -1 3
4 4 7 7
1 0
0 -3
Выходные данные
-1
ограничение по времени на тест
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
ограничение по времени на тест
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.0 second;
ограничение по памяти на тест
64 megabytes

Чтобы помешать появлению СЭС в лагере, администрация ЛКШ перекопала единственную дорогу, соединяющую «Берендеевы поляны» с Судиславлем, теперь проехать по ней невозможно. Однако, трудности не остановили инспекцию, хотя для СЭС остается только одна возможность — дойти до лагеря пешком. Как известно, Судиславль находится в поле, а «Берендеевы поляны» — в лесу.

  • Судиславль находится в точке с координатами $(0,\,1)$.
  • «Берендеевы поляны» находятся в точке с координатами $(1,\,0)$.
  • Граница между лесом и полем — горизонтальная прямая $y = a$, где $a$ — некоторое число $(0 \le a \le 1)$.
  • Скорость передвижения СЭС по полю составляет $V_p$, скорость передвижения по лесу — $V_f$. Вдоль границы можно двигаться как по лесу, так и по полю.

Администрация ЛКШ хочет узнать, сколько времени у нее осталось для подготовки к визиту СЭС. Она попросила вас выяснить, в какой точке инспекция СЭС должна войти в лес, чтобы дойти до «Берендеевых полян» как можно быстрее.

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

В первой строке входного файла содержатся два положительных целых числа $V_p$ и $V_f$ $(1 \le V_p, V_f \le 10^5)$. Во второй строке содержится единственное вещественное число — координата по оси $Oy$ границы между лесом и полем $a$ $(0 \le a \le 1)$.

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

В единственной строке выходного файла выведите вещественное число с точностью не менее 8 знаков после запятой — координата по оси $Ox$ точки, в которой инспекция СЭС должна войти в лес.

Примеры
Входные данные
5 3
0.4
Выходные данные
0.783310604
Входные данные
5 5
0.5
Выходные данные
0.500000000

Страница: 1 2 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест