3517번 - Kids Like Cakes 스페셜 저지다국어

Kids like cakes. It’s obvious. In this problem, we consider only cakes having the form of a convex polygon, as viewed from above.

Every cake needs to be split into pieces. In this problem, every piece should have a form of a non-degenerate triangle with vertices at original cake’s vertices. The pieces may not intersect, and their union should form the original cake.

Some kids also like fairness. Let’s call the unfairness number of a cake the maximal possible difference between the areas of the largest and the smallest pieces of it.

Your task is to find the unfairness number of a given cake.

The first line of the input file contains a single integer number n — the number of vertices of the cake (4 ≤ n ≤ 5000). The following n lines contain two integers x_i, y_i each — the coordinates of the vertices (−10⁸ ≤ x_i, y_i ≤ 10⁸).

The first line of the output file must contain a single number with exactly one digit after the decimal point — the unfairness number of the cake.

The following two lines must describe the way to split the cake to get such unfairness number. The first of them should contain three indices of vertices of the largest piece in it. The second one should contain three indices of vertices of the smallest piece. Vertices are numbered from 1 to n.