--->
144 задач
<---
Источники
#1021
Темы:
[Элементарная геометрия]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Будем говорить, что для наблюдателя лес является дремучим, если из своего текущего положения наблюдатель видит только деревья. Вам дана карта леса и координаты точки, в которой находится наблюдатель. Требуется определить, кажется ли лес дремучим данному наблюдателю.
На карте леса все деревья изображаются кругами. При этом в лесу бывают сросшиеся деревья (изображения таких деревьев на карте пересекаются), также одно дерево может находиться внутри другого. Точка, в которой стоит наблюдатель, не лежит внутри или на границе ни одного из деревьев.
Входные данные
Во входном файле содержится сначала целое число N — количество деревьев (1N50000). Затем идут два числа, задающих координаты наблюдателя. Затем идет N троек чисел, задающих деревья. Первые два числа задают координаты центра, а третье — радиус. Все координаты задаются точно, и выражаются вещественными числами не более чем с 2 знаками после десятичной точки, по модулю не превосходящими 100000.
Выходные данные
В первой строке выходного файла должно содержаться сообщение YES, если лес является дремучим, и NO иначе. Во втором случае вторая строка выходного файла должна содержать координаты точки, глядя в направлении которой наблюдатель не видит деревьев (то есть луч, вдоль которого смотрит наблюдатель не проходит внутри деревьев и не касается ни одного из деревьев). Координаты нужно вывести не менее, чем с 3 знаками после десятичной точки. Координаты не должны превышать 300000. Расстояние между выданной точкой и наблюдателем должно быть не меньше 1.
Примеры
Входные данные
4 1 1 7 7 6 -4 6 5 6 -4 5 -5 -5 6
Выходные данные
YES
#1046
Темы:
[Элементарная геометрия]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
В пространстве с прямоугольной системой координат находятся два куба. Про них известно следующее:
- сторона каждого куба равна 2,
- центр (т.е. центр симметрии) каждого куба совпадает с началом данной системы координат,
- координаты вершин >первого куба A1A2A3A4A5A6A7A8 следующие: A1(1, 1, 1), A2(1, –1, 1), A3(–1, –1, 1), A4(–1, 1, 1), A5(1, 1, –1), A6(1, –1, –1), A7(–1, –1, –1), A8(–1, 1, –1),
- вершины второго куба B1B2B3B4B5B6B7B8 пронумерованы так, что путем поворота кубы можно совместить, и при этом совместятся соответствующие их вершины (A1 и B1, A2 и B2, … , A8 и B8)
- координаты вершин второго куба даны во входном файле.
Требуется найти объем пересечения (т.е. общей части) этих кубов.
Входные данные
Во входном файле записаны 8 троек действительных чисел – координаты вершин второго куба B1B2B3B4B5B6B7B8.
Выходные данные
В выходной файл выведите одно число – искомый объем пересечения кубов. Ответ не должен отличаться от верного более чем на 0.00001.
Примеры
Входные данные
1.0000000000 -1.0000000000 1.0000000000 1.0000000000 -1.0000000000 -1.0000000000 -1.0000000000 -1.0000000000 -1.0000000000 -1.0000000000 -1.0000000000 1.0000000000 1.0000000000 1.0000000000 1.0000000000 1.0000000000 1.0000000000 -1.0000000000 -1.0000000000 1.0000000000 -1.0000000000 -1.0000000000 1.0000000000 1.0000000000
Выходные данные
8.00000000000000000000
Входные данные
1.4142135623730950488016887242097 0 1 0 -1.4142135623730950488016887242097 1 -1.4142135623730950488016887242097 0 1 0 1.4142135623730950488016887242097 1 1.4142135623730950488016887242097 0 -1 0 -1.4142135623730950488016887242097 -1 -1.4142135623730950488016887242097 0 -1 0 1.4142135623730950488016887242097 -1
Выходные данные
6.62741699796952078000
#1049
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Заключительный этап,
2004,
1 день,
Задача C
]
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
64 megabytes
Горнолыжник, готовясь к соревнованиям, нарисовал на бумаге схему горнолыжной трассы для выбора оптимального маршрута спуска. На схеме расположенные на трассе ворота представлены горизонтальными отрезками. Никакая пара ворот не имеет общих точек.
Маршрут должен представлять собой ломаную, начинающуюся в точке старта на вершине горы и заканчивающуюся в точке финиша у ее подножия. Маршрут выбирается таким образом, что y-координата каждой следующей вершины ломаной оказывается строго меньше y-координаты предыдущей вершины. Один из возможных маршрутов представлен на рисунке.
За каждые ворота, через которые не проходит маршрут, лыжнику начисляются штрафные очки. Общий штраф за спуск по маршруту вычисляется как сумма длины маршрута и штрафных очков за непройденные ворота.
Требуется написать программу, которая определяет, какой минимальный общий штраф горнолыжник может получить при прохождении трассы.
Входные данные
В первой строке входного файла задано число N - количество ворот на трассе (0 ≤ N ≤ 500), в следующих двух строках заданы Sx, Sy, Fx, Fy - координаты точек старта и финиша соответственно. В каждой из следующих N строк записаны четыре числа ai, bi, yi, ci - x-координаты левого и правого концов ворот, y-координата ворот и штраф за непрохождение данных ворот (ai < bi, Fy < yi < Sy, ci - целое число, 0 ≤ ci ≤ 10000). Все координаты - целые числа, не превосходящие по модулю 10000.
Выходные данные
В выходной файл выведите наименьший возможный общий штраф за прохождение трассы с точностью не менее 4 знаков после десятичной точки.
Система оценки
Потестовая.
Примеры
Входные данные
4 3 6 3 1 5 7 4 1 4 5 5 10 1 2 4 5 2 5 2 0
Выходные данные
7.8126
#1100
Темы:
[Элементарная геометрия]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Муха летит вдоль прямой. Если нанести на эту прямую координаты, то можно сказать, что в 0-й момент времени муха пролетает точку с координатой 0 и летит в положительном направлении со скоростью V. Муха может менять свою скорость, однако ускорение мухи не может по модулю превышать величины A, в частности, муха не может мгновенно остановиться. Максимальная скорость мухи не может превышать по модулю величины W.
Известно, что в момент времени T по прямой ударит мухобойка, которая полностью накроет отрезок от точки C до точки D. Если муха в этот момент окажется на этом отрезке, она погибнет.
Напишите программу, которая определит, есть ли у мухи шанс спастись, и если есть, то выведет, что должна муха для этого делать.
Входные данные
Во входном файле заданы числа V, W, A, T, C, D. Все числа целые. 0≤V≤W≤1000, 0≤A≤1000, 0<T≤1000, –1000000≤C≤D≤1000000.
Выходные данные
Если муха может спастись, выведите, как она должна для этого лететь. Для этого выведите последовательность команд для мухи. Количество команд не должно превышать 100. Каждая команда задается двумя числами Ti, Ai, которые обозначают, что в течение времени Ti муха должна лететь с ускорением Ai. Ti и Ai не обязаны быть целыми, Ti должны быть положительны (не могут быть равны 0), сумма всех Ti должна быть равна T с точностью до 10-6.
Если, в рамках указанных ограничений, муха спастись не сможет, в выходной файл выведите одно число –1 (минус 1).
Примечания
Муха может сначала снизить скорость до 0, а затем полететь в обратную сторону (см. примеры).
Если в момент времени T муха окажется на концах отрезка, т.е. в точке C или D, она все равно погибнет.
Комментарии к примерам тестов
1. Муха не сможет спастись.
2. Сначала в течение времени 0.2 муха летит с постоянной скоростью 10, а затем ускоряется с ускорением 4
3. Муха сначала тормозит с ускорением -5, а затем с этим же ускорением начинает лететь в обратную сторону. Набрав скорость 10, муха продолжает лететь с ней без ускорения.
Примеры
Входные данные
10 10 5 1 -100 100
Выходные данные
-1
Входные данные
10 20 5 1 9 11
Выходные данные
1 5
Входные данные
10 10 5 5 0 1000
Выходные данные
4.000000000000000000 -5 1.000000000000000000 0
#1102
Темы:
[Элементарная геометрия]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
На плоскости дано N горизонтальных отрезков. Будем говорить, что прямая пересекает отрезок, если у этой прямой и этого отрезка есть хотя бы одна общая точка (в том числе прямая пересекает отрезок, если она проходит через один из его концов). Требуется найти прямую, пересекающую все отрезки, или установить, что такой нет.>
Входные данные
В первой строке входного файла находится единственное число N. В каждой из следующих N строк содержатся по три целых числа Pi, Qi, Ri, описывающих отрезки: соответствующий отрезок соединяет точки (Pi, Ri) и (Qi, Ri). Никакие два отрезка не лежат на одной прямой.
1≤N≤10000, Pi<Qi, все числа по модулю не превосходят 10000.
Выходные данные
В случае, если искомая прямая существует, выведите в выходной файл коэффициенты ее уравнения (будем задавать прямую уравнением вида A∙x+B∙y+C=0, где x, y – координаты точек прямой, A, B, C – такие коэффициенты, что указанному уравнению удовлетворяют все точки прямой, и только они; соответственно, чтобы задать прямую, нужно задать три числа – A, B, C).
Коэффициенты уравнения должны быть целыми и не должны превосходить по модулю 109 (гарантируется, что при наличии решения такие A, B, C существуют).
Если прямой не существует, выведите в выходной файл сообщение “No solution” (без кавычек).
Примеры
Входные данные
3 0 1 0 0 1 1 0 1 2
Выходные данные
1 0 0
Входные данные
5 0 2 0 2 4 1 1 3 2 1 3 -1 1 3 -2
Выходные данные
3 -1 -5
Входные данные
3 0 1 0 1 2 1 -2 -1 2
Выходные данные
No solution
Выбрано
:
|