아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

요새 건설

시간 제한7초메모리 제한256 MB

요약
주어진 점 중 최대 네 점을 골라 만들 수 있는 볼록 다각형 중 넓이가 가장 큰 값을 구합니다.
난이도

보통10점 중 6점

유형
기하, 완전 탐색
정답자
아직 제출이 없습니다

문제

감시탑은 최대 4개까지 설치할 수 있고, 각 탑은 주어진 후보 좌표 중에서만 고를 수 있다. 탑을 꼭짓점으로 하는 볼록 다각형 기지 중 넓이가 가장 큰 것을 구하라.

입력

첫 줄에 테스트 수 TT가 주어진다. 각 테스트는 후보 점의 개수 nn과 nn개의 서로 다른 좌표 (x,y)(x,y)로 주어진다.

출력

각 테스트마다 가능한 최대 기지 넓이를 출력한다. 값이 반정수이면 소수 첫째 자리까지 정수.5 형식으로 출력한다.

예제1

  1. 예제 1

    입력
    3
6
0 0
3 7
10 0
11 6
0 10
10 10
5
0 0
-2 -2
3 -2
0 1
0 3
10
3 1
4 1
5 9
2 6
5 3
5 8
9 7
9 3
2 3
8 4
    예상 출력
    100
12.5
31