--->
8 задач
<---
#34
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
На плоскости нарисовали прямоугольник, после чего его разрезали прямыми. Напишите программу, которая вычислит, сколько из полученных кусков исходного прямоугольника имеют треугольную форму.
Рисунок, соответствующий 1-му примеру входных и выходных данных
Входные данные
Сначала на вход программы поступают два положительных числа X и Y, задающих координаты правого верхнего угла прямоугольника. Прямоугольник расположен в системе координат так, что левый нижний его угол имеет координаты 0,0 и стороны параллельны осям координат.
Далее вводится целое число N — количество разрезов (1≤N≤200). Затем описываются сами разрезы. Каждый разрез делался вдоль некоторой прямой. Каждая прямая, соответствующая разрезу, задается тремя числами A, B, C такими, что все точки (x,y) этой прямой (и только они) удовлетворяют уравнению Ax+By+C=0 (при этом всегда A2+B2>0).
Все входные данные (кроме N) – вещественные числа, заданы с двумя знаками после десятичной точки и не превышают 104. Никакие две прямые не совпадают между собой и не содержат сторон прямоугольника. Каждый разрез проходит через точки внутри исходного прямоугольника.
Выходные данные
Выведите одно целое число — количество частей исходного прямоугольника, имеющих треугольную форму.
Система оценки
1 балл получат программы, правильно решающие задачу при ограничении 1≤N≤50.
Примеры
Входные данные
5.00 1.00 3 1.00 -2.00 0.00 1.00 -3.00 -2.00 1.00 1.00 -4.00
Выходные данные
3
Входные данные
4.00 2.00 2 1.00 -2.00 0.00 1.00 2.00 -4.00
Выходные данные
4
#43
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
При игре в лапту одна команда ловит мяч и пытается осалить им бегущего. Игрок другой команды должен, перед тем как бежать, ударить мяч в поле. Известно, на какое максимальное расстояние он может ударить, а также скорости и начальные координаты игроков другой команды. Требуется выбрать направление и силу удара так, чтобы минимальное время, которое потребуется другой команде, чтобы поднять мяч с земли, было наибольшим. (Пока мяч летит, игроки стоят на местах.)
Входные данные
В первой строке входных данных содержатся два числа: D — максимальное расстояние удара и N — количество соперников на поле (D и N натуральные числа, D ≤ 1000, N ≤ 200). В следующих N строках задается по три числа – начальные координаты xi и yi и максимальная скорость vi соответствующего игрока (скорости и координаты — целые числа, –1000 ≤ xi ≤ 1000, 0 ≤ yi ≤ 1000, 0 < vi ≤ 1000), никакие два игрока не находятся изначально в одной точке. Игрок, бьющий мяч, находится в точке с координатами (0,0). Мяч выбивается в точку с неотрицательной ординатой (y ≥ 0).
Выходные данные
Выведите сначала время, которое потребуется игрокам, чтобы добежать до мяча, а затем координаты точки, в которую нужно выбить мяч. Если таких точек несколько, выведите координаты любой из них. Время и координаты нужно вывести с точностью 10–3.
Оценка задачи
1 балл получат программы, которые верно работают, когда в поле не более двух соперников.
Примеры
Входные данные
10 2 1 1 1 -1 1 1
Выходные данные
9.05539 0.00000 10.00000
#860
Источники:
[
Командные олимпиады,
Московская командная олимпиада,
9-11 классы,
2008,
Лига А,
Задача G
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Поверхность Земли в горной местности можно представить в виде ломаной линии. Вершины ломаной расположены в точках (x1, y1), (x2, y2),…,(xN, yN), при этом xi<xi+1.
Обычный горный маг находится в точке (x1, y1) и хочет попасть в точку (xN, yN). При этом он может перемещаться только пешком. Он может ходить по поверхности Земли (т.е. вдоль ломаной). А может сотворить в воздухе мост и пройти по нему. Мост может соединять две вершины ломаной: мост не может начинаться и заканчиваться не в вершине ломаной, и мост не может проходить под землей (в том числе не может быть туннелем в горе), но мост может каким-то своим участком проходить по поверхности земли. Длина моста не может быть больше R. Суммарно маг может построить не более K мостов.
Какое наименьшее расстояние придется пройти магу, чтобы оказаться в точке (xN, yN).
Входные данные
Вводится сначала натуральное число N (2≤N≤100). Затем водится натуральное число K (1≤K≤100) — максимальное количество мостов. Далее вводится целое число R (0≤R≤10000) — максимальная возможная длина моста. Далее вводятся координаты (x1, y1), (x2, y2),…,(xN, yN). Все координаты – целые числа, не превышающие по модулю 10000, для всех i от 1 до N–1: xi<xi+1.
Выходные данные
Выведите одно число — минимальную длину пути, которую придется пройти магу (как по земле, так и по мостам). Ответ выведите не менее чем с 5 цифрами после десятичной точки.
Примеры
| Входных данные | Выходные данные |
| 5 2 5 0 0 2 2 3 -1 4 1 5 0 | 6.47871 |
| 9 2 3 1 2 2 1 3 3 5 -1 6 2 7 0 8 1 9 0 10 1 | 14.93498 |
#1189
Темы:
[Элементарная геометрия]
Источники:
[
Командные олимпиады,
Московская командная олимпиада,
9-11 классы,
2007,
Лига А,
Задача G
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
На новой станции метро, которую планируют открыть в конце этого года, будет N эскалаторов (эскалаторы пронумерованы подряд числами от 1 до N). Эскалаторы имеют длину L и расположены на расстоянии H друг от друга. Шириной эскалатором пренебрежем. Между каждыми двумя соседними эскалаторами (точно посередине) будет установлен ряд ламп. В ряду будет K ламп. Лампы устанавливаются по следующему принципу: всю длину эскалатора L разбивают на K равных отрезков и в середине каждого отрезка устанавливают по лампе (см. рисунок). Всего будет установлено (N–1)*K ламп.
На приведенном рисунке N=4 (эскалаторы показаны жирными <горизонтальными линиями), L=20, H=4, K=5.
Васе удалось проникнуть на эту станцию еще до ее открытия, и даже прокатиться на эскалаторе. Он выбрал эскалатор номер J. Посчитайте, в скольких точках эскалатора (включая его начало и конец) Вася будет видеть не все лампы (так как их будут загораживать другие лампы).
Входные данные
Во входном файле записаны числа N, L, H, K, J. Все числа — натуральные. 2≤N≤35, 1≤L≤1000, 1≤H≤1000, 1≤K≤35, 1≤J≤N.
Выходные данные
В выходной файл выведите одно число — ответ задачи.
Примеры
Входные данные
2 20 4 5 1
Выходные данные
0
Входные данные
4 20 4 5 2
Выходные данные
11
#1244
Темы:
[Элементарная геометрия]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Просека — эта такая прямая линия, которая проходит через лес (то есть деревья есть как с одной стороны от этой линии, так и с другой), и при этом она не проходит ни через одно из деревьев леса, а также не касается деревьев. Будем говорить, что лес является дремучим, если в нем нет ни одной просеки.
На плане леса все деревья изображаются кругами. Никакие два круга не пересекаются и не касаются друг друга. Требуется по этому плану определить, является ли лес дремучим.
Входные данные
Во входном файле содержится сначала целое число N — количество деревьев (1N200). Затем идет N троек чисел, задающих деревья. Первые два числа задают координаты центра, а третье — радиус. Все данные задаются точно, и выражаются вещественными числами, не более чем с 2 знаками после десятичной точки, по модулю не превосходящими 1000.
Выходные данные
В первой строке выходного файла должно содержаться сообщение YES, если лес является дремучим, и NO иначе. Во втором случае вторая строка выходного файла должна содержать координаты двух точек, через которые проходит просека. Все координаты нужно выводить с восемью знаками после десятичной точки, координаты не должны превышать 2000, и расстояние между выданными точками должно быть не меньше 100.
Примеры
Входные данные
3
0.00 30.00 25.00
0.00 -30.00 25.00
40.00 0.00 16.00
Выходные данные
NO
-833.3333340000 -552.7707973875
833.3333340000 552.7707973875
Входные данные
3
0.00 30.00 29.00
0.00 -30.00 29.00
40.00 0.00 19.00
Выходные данные
YES
Выбрано
:
|