Задача A. Столкновение шариков ≡

Условие

По горизонтальной плоской поверхности катятся два шарика радиуса R метров каждый. В начальный момент времени шарики имеют координаты центров (x₁, y₁) и (x₂, y₂) метров, а также проекции скоростей на координатные оси (dx₁, dy₁) и (dx₂, dy₂) метров в секунду соответственно.

Требуется найти время в секундах, спустя которое шарики столкнутся, или определить, что этого не произойдёт.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

1
0 0 10 0
50 0 -10 0

2.4

Задача B. Крайние проекции ≡

Условие

Глеб нарисовал на координатной плоскости N точек и стал проецировать их в разных направлениях на ось ординат.

Сначала Глеб выбирает направление проецирования — наклоняет линейку под определённым углом. Затем, параллельно перемещая линейку, Глеб прикладывает её по очереди ко всем точкам и для каждой точки находит точку пересечения линейки с осью ординат. Эта точка пересечения и есть проекция точки на ось ординат.

Глеб проецирует точки на ось ординат во всех возможных направлениях. Сначала он располагает линейку вертикально, а затем начинает разворачивать её против часовой стрелки. При этом угловой коэффициент наклона линейки возрастает от −∞ до +∞.

При каждом направлении проектирования найдётся точка, которая спроецируется "выше всех" (будет иметь наибольшую ординату проекции). Назовём такую точку крайней точкой.

При определённых наклонах линейки крайняя точка изменяется. Требуется написать программу, принимающую на вход координаты точек и выводящую для каждого изменения крайней точки новый номер и угловой коэффициент наклона линейки, при котором произошло это изменение.

Формат входного файла

Первая строка входного файла содержит целое число N — количество точек.

Далее следуют N строк, каждая из которых содержит пару вещественных чисел x_i y_i — координаты точки.

Формат выходного файла

Выходной файл должен содержать (2 M+1) чисел, где M — количество изменений крайней точки.

Первое число — это номер точки, которая будет крайней при угловом коэффициенте наклона линейки, стремящемся к −∞. Далее идут M пар чисел k_i j_i — угловой коэффициент наклона линейки, при котором происходит изменение крайней точки, и номер точки, которая станет крайней после изменения. Пары чисел должны быть выведены в порядке возрастания углового коэффициента.

Угловой коэффициент должен быть выведен с точностью не менее 3-х знаков после запятой.

Ограничения

1 ≤ N ≤ 1000

1 ≤ x_i, y_i ≤ 100

Гарантируется, что при любом угловом коэффициенте выше всех не могут проецироваться более двух точек.

Примеры тестов

10
5.0 3.0
6.5 2.5
9.0 2.0
3.5 4.0
1.0 3.1
7.5 1.75
2.0 2.6
6.0 3.5
10.0 1.0
9.0 1.2

9
-1.000 3
-0.500 8
-0.200 4
0.360 5

Problem C. Smooth convex hull ≡

Statement

There are N points on a plane. Convex hull is such a convex polygon with the least possible area, that all the given points are either within its interior or belong to its border.

Let's say that one convex polygon is smoother that the other one if it's sharpest angle is more obtuse than the sharpest angle of the other one.

Your task is to make the convex hull of the given set of points as smooth as possible. To do it you are allowed to exclude no more than one point from the given set.

Input file format

Output file format

Output file must contain a single number: the sharpest angle (in radians) in the most smooth convex hull with absolute error less than 0.01.

Constraints

3 ≤ N ≤ 1000

1 ≤ x_i, y_i ≤ 10⁶

Sample tests

5
1 1  2 10  1 3  3 1  3 3 

1.57

4
1 1  1 3  3 1  3 3 

1.57