Problem A. Falling Cards
Statement
It is hard to make the playing card stand on its edge, however, some patient person managed to put N of them upon the desk in such a way that each cards stands on its shorter edge. The top-down view of that desk with cards upon it can be represented with the set of line segments with coordinates (xi, yi) to (vi, wi). The segments do not intersect.
The first card falls flat on its side, causing any card it touches to fall down also. The angle between vector (x1, y1)-(v1, w1) and the falling direction of the first card is equal to 90 degrees (measured counter-clockwise). If card A touches card B, the direction of B's fall is chosen so that the continuation of the direction vector does not cross the line containing segment A. Input data are guaranteed to never contain:
1) a card falling exactly perpendicular to the other and
2) a falling card that touches more than one of still standing cards.
Your program must determine which cards will fall, and which shall remain standing.
Input file format
The first line of input file contains a numbers N H - the number of cards and the floating point height of a card. Each of the following N lines contains four floating-point numbers x
i y
i v
i w
i - coordinates of cards separated by spaces.
Output file format
The output file must contain the list of fallen cards' numbers, sorted in increasing order and separated by spaces.
Constraints
1 ≤ N ≤ 100
Sample tests
| No. |
Input file (input.txt) |
Output file (output.txt) |
|---|
| 1 |
3 100
10 10 50 40
10 0 50 30
20 90 20 20
|
1 3
|
Задача B. Бармаглот под одеялом
Условие
Мальчик Петя придумал страшного Бармаглота, хватающего детей.
Когда Петя зашёл в свою комнату, чтобы ложиться спать, он увидел, что одеяло на кровати
очень похоже на Бармаглота. Требуется по заданной форме одеяла и форме Бармаглота
определить, может ли Бармаглот поместиться под одеялом, и, соотвественно,
следует ли Пете испугаться и заплакать или спокойно пойти спать.
Одеяло и Бармаглот имеют форму ломаных, заданных целочисленными координатами вершин
(x1, y1),
(x2, y2), …
(xN, yN)
для одеяла,
(u1, v1),
(u2, v2), …
(uM, vM)
для Бармаглота.
При этом
xi + 1 > xi и
ui + 1 > ui для всех i.
Чтобы спрятаться под одеялом, Бармаглот должен полностью под него поместиться,
т.е. описывающая его ломаная должна целиком находиться ниже ломаной, описывающей одеяло.
Касания ломаных разрешены.
Формат входного файла
Во входном файле расположены числа
N
x1 y1
x1 y1 …
xN yN
M
u1 v1
u1 v1 …
uM vM
Формат выходного файла
Выходной файл должен содержать единственную строку
CRY,
если Бармаглот может поместиться под одеялом или
SLEEP, если не может.
Ограничения
3 ≤
M,
N ≤ 100,
0 ≤
xi,
yi,
ui,
vi ≤ 10000,
x1 =
u1,
xN =
uM.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
3 0 0 5 5 6 0
4 0 0 2 1 5 5 6 0
|
CRY
|
Задача C. Сухой фотограф
Условие
В некотором городе имеется достопримечательность - прямоугольная площадь размером X на Y метров, на которой работают N фонтанов. Турист желает посетить эту площадь и сделать несколько фотографий. Однако если при фотографировании находиться от какого-либо из фонтанов на расстоянии меньше R метров, фотоаппарат может быть поврежден брызгами воды. Помогите фотографу найти безопасную точку съёмки.
Требуется по координатам фонтанов определить точку на площади, удалённую от каждого из них не менее чем на R метров, или определить, что такой точки не существует. Если таких точек более одной, вывести любую из них.
Обратите внимание, что стоять в точности на границе окружности или прямоугольника разрешено.
Формат входного файла
В первой строке входного файла содержатся числа X Y N R, в каждой из следующих N строк - координаты x
i y
i i-го фонтана. Числа X Y R во входном файле — вещественные.
Формат выходного файла
В выходном файле должны, содержаться два вещественных числа - координаты сухой точки. Если такой точки не существует, следует вывести значения -1 -1.
Проверка результатов будет осуществляться путём подстановки координат точки в неравенства, задающие внутренность каждого круга. Эти вычисления будут производиться с использованием вещественных чисел двойной точности (double).
Ограничения
1 <= N <= 100, 1 <= X, Y, R <= 10
6.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
100 100 4 50
0 0
100 0
0 100
100 100
|
50 50
|
