Close Triangles
시간 제한7초메모리 제한1024 MB
3n개의 점을 n개의 삼각형으로 나누어 가장 큰 삼각형과 가장 작은 삼각형의 넓이 차이를 최소로 만들고, 그 차이를 소수 첫째 자리까지 반올림해 출력한다.
문제
When dealing with children, you want to divide things as evenly as possible. In particular, the child who receives the least will compare themselves to the child who receives the most, so you’d like these two values to be as close to each other as possible.
Given 3n points, form n triangles (using each point exactly once) such that the difference between the largest triangle (in area) and the smallest triangle (in area) is as small as possible. That is, we want these two triangles to be as close to each other (in area) as possible.
입력
The first input line contains an integer, n (2 ≤ n ≤ 5), indicating the number of triangles to be formed. This is followed by 3n input lines. Each of these lines provides the x and y coordinates of a point. Assume that all of these input values are integers between 1 and 103, inclusive. Also assume that all the points are distinct and we can form n triangles. It is also guaranteed that no triplet of the given points will be colinear.
출력
Print the difference (in area) between the largest and smallest triangles, rounded to one decimal point, e.g., 0.74 should be printed as 0.7 and 0.75 should be printed as 0.8.