Задача A. Бармаглот под одеялом
Условие
Мальчик Петя придумал страшного Бармаглота, хватающего детей.
Когда Петя зашёл в свою комнату, чтобы ложиться спать, он увидел, что одеяло на кровати
очень похоже на Бармаглота. Требуется по заданной форме одеяла и форме Бармаглота
определить, может ли Бармаглот поместиться под одеялом, и, соотвественно,
следует ли Пете испугаться и заплакать или спокойно пойти спать.
Одеяло и Бармаглот имеют форму ломаных, заданных целочисленными координатами вершин
(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
|
Задача B. Новогодний пузырь
Условие
Новогодняя вечеринка проходит в плоском прямоугольном зале с координатами левого нижнего угла (0, 0),
а правого верхнего — (1000, 1000).
С потолка зала свешивается мишура в виде
N прямых тонких вертикальных лент
с координатами нижних концов (
xi, yi).
Один из гостей запустил мыльный пузырь радиуса
R.
Первоначально центр пузыря находился в точке (
x, R).
Пузырь полетел вертикально вверх до столкновения с
лентой мишуры или потолком, после чего лопнул.
Требуется определить, с чем именно он столкнулся.
Формат входного файла
В первой строке входного файла содержатся числа
N R x, в следующих
N строках
содержатся вещественные числа
xi yi.
Числа в строке разделены пробелами. Значения всех
xi во входном файле различны.
Формат выходного файла
В выходном файле должно содержаться единственное число — номер ленты (во входном файле), либо 0 (нуль),
если пузырь долетел до потолка. Если пузырь одновременно столкнулся с несколькими лентами (и, возможно, потолком),
вывести номер самой левой ленты.
Ограничения
0 ≤ N ≤ 100, 0 < R ≤ 50, R ≤ x < 1000 − R
0 < xi < 1000, 0 < yi < 1000
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
3 20.0 50
30 70
50 81.5
70 79
|
2
|
Problem C. Half of a convex polygon
Statement
You need to divide a non-degenerate convex polygon with a horizontal
line into two parts of equal area.
The polygon is specified by N vertices in the clockwise order.
Input file format
Input file contains integer
N, then
N
pairs of floating-point numbers
xi yi
describing the vertices of the polygon.
Output file format
Output a single number — the ordinate of the horizontal line dividing
the polygon as requested. The result must be rounded to 10
-2.
Constraints
3 ≤ N ≤ 1000000
1 ≤ xi, yi ≤ 1000000
Sample tests
| No. |
Input file (input.txt) |
Output file (output.txt) |
|---|
| 1 |
4
1 1 1 3 3 3 3 1
|
2
|
