Problem A. Half of a convex polygon ≡

Author:T. Chistyakov, A. Klenin
Input file: input.txt   Time limit:2 sec
Output file: output.txt   Memory limit:24 Mb

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

Problem B. Smooth convex hull ≡

Author:T. Chistyakov, A. Klenin
Input file: input.txt   Time limit:3 sec
Output file: output.txt   Memory limit:64 Mb

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

Input file contains integer N, then N pairs of real numbers xi yi describing given points. There are no duplicate points in the input file.

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 ≤ xi, yi ≤ 106

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
5
1 1  2 10  1 3  3 1  3 3 

1.57
2 
4
1 1  1 3  3 1  3 3 

1.57

Задача C. Наилучшее приближение ≡

Автор:Зимние сборы 2005
Входной файл: best.in   Ограничение времени:2 сек
Выходной файл: best.out   Ограничение памяти:64 Мб

Условие

Нередко при решении статистических задач требуется найти прямую, расположенную в некотором смысле посередине данного набора точек. В этой задаче требуется минимизировать сумму квадратов расстояний от точек данного набора до прямой.

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

В первой строке входного файла задано число n. В последующих n строках заданы координаты точек (xi, yi).

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

В первой строчке необходимо вывести минимум суммы квадратов расстояний от прямой до точек набора. Во второй строчке должны быть выведены числа a, b, c из уравнения прямой в виде ax+by=c. Числа должны удовлетворять условиям a^2+b^2=1, c≥0. Все числа необходимо выводить с 6 знаками после запятой.

Ограничения

1 ≤ n ≤ 100 000, Все координаты — целые числа, по модулю не превосходящие 1000.

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

№ Входной файл (best.in) Выходной файл (best.out)
1 
3
0 0
1 0
1 1
 
0.333333
0.707107 -0.707107 0.235702
0.028s 0.004s 11