기하 문제 연구

문제 정보

문제

대학원생이 된 kimyolo는 기하 문제에 대해서 연구하고 있다. kimyolo와 함께 기하 문제를 풀어보자.
N각 볼록다각형과 함수 F와 G가 주어진다. 함수 F와 G는 아래와 같이 정의된다.

F(i) = i번째 점을 제외하고, 나머지 N-1개의 꼭지점 중에 3개의 꼭지점을 임의로 리턴한다.

G(i) = F(i)의 꼭지점으로 그려지는 삼각형의 넓이의 기대값

( 1 ≤ i ≤ N )

G(1) 부터 G(N) 중에 가장 작은 값을 구하라.

입력

첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. (T ≤ 30)

각 테스트 케이스의 첫 번째 줄에는 꼭지점의 개수를 의미하는 자연수 N이 주어진다. ( 4 ≤ N ≤ 500 )

그리고 그 다음 N개 줄에 걸쳐 i번째 꼭지점의 좌표가 Xi Yi 형태로 주어진다.

(-100 ≤ Xi, Yi ≤ 100, Xi와 Yi는 실수)

입력되는 좌표를 순서대로 연결하면 볼록다각형이 그려진다.

출력

가장 작은 G(i)값을 소수점 첫째자리에서 반올림하여 출력한다. ( 1 ≤ i ≤ N )

예제 입력

2
5
-4 -8
8 -6
8 -3
2 9
-10 0
5
-4 -8
8 -6
8 5
-4 9
-9 1

예제 출력

41
72

노트

0개의 댓글이 있습니다.