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
|
Problem B. Road Accident
Statement
Two cars crashed on the road, receiving some damage each, and
raising the usual question: "Who to blame?". To answer this, it is essential to
thoroughly reconstruct the sequence of events. By gathering witness testimonies
and analyzing tire tracks, positions and speeds of cars just before the impact
were determined.
From these positions until the crash the cars moved straight forward.
Your program must, given the available data, calculate for each car
what part of it first came into contact with the other car. Parts are numbered as
shown on the picture.
Input file format
Input file contains twelve floating point numbers:
x1 y1 u1 v1 w1 s1 x2 y2 u2 v2 w2 s2, where
(x, y) and
(u, v) — coordinates of
back-left and forward-left corners of the car,
w — width of the car,
s — speed of the car.
Output file format
Output file must contain two integers:
p1 p2, where
p — number of part which
first contacted the other one (if two parts came into contact simultaneously,
output the lesser of the part numbers),
Constraints
1 ≤ xi, yi, ui, vi, wi ≤ 106, 0 ≤ si ≤ 106.
Input data is such that a crash certainly happens. Initially cars don't have common points.
Sample tests
| No. |
Input file (input.txt) |
Output file (output.txt) |
|---|
| 1 |
1.0 2.0 10.0 2.0 1.0 10.0
50.0 1.0 40.0 1.0 1.0 20.0
|
2 2
|
| 2 |
1 1 10 1 1 20
40 1 50 1 1 10
|
2 1
|
Задача C. Площадь пирога
Условие
Раз на раз не приходится. И теперь пирог получился в форме невыпуклого многоугольника с N вершинами.
Пытаться разрезать его на треугольники, теперь, кажется, совсем бесполезно. Поэтому хозяйка решила поделить его,
руководствуясь иными, ничуть не менее очевидными соображениями. А именно — пусть всем достанутся куски одинаковой площади.
Однако теперь, чтобы претворить ее план в жизнь нужно посчитать площадь всего пирога. Напишите такую программу.
Формат входного файла
Первая строка входного файла содержит число N — количество вершин многоугольника.
Вторая строка содержит N пар разделенных пробелами действительных чисел xi yi —
координаты вершин многоугольника в порядке обхода по или против часовой стрелки.
Формат выходного файла
В выходной файл выведите площадь многоугольника с точностью до четырех знаков после запятой.
Ограничения
3 ≤ N ≤ 500
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
6
0 0 1 1 2 1 3 0 2 -1 1 -1
|
4.0000
|
