Код Архимеда 2021 - Smooth convex hull

Problem B. Smooth convex hull ≡

problems
visible spaces
basic formulae
wide text
editor

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

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 x_i y_i 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 ≤ x_i, y_i ≤ 10⁶

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`