즉석 야외 미술관

예술가 Cody-Jamal은 최근 자신의 최신 그림들을 즉석 야외 미술관에서 선보여 모든 힙스터 친구들보다 더 힙해지기로 했다. 그는 들판에 나타나 그림 몇 점을 설치하고 전시할 예정이다.

들판에는 N개의 기둥이 있으며, 그중 3개로 이루어진 어떤 부분집합도 한 직선 위에 있지 않다(이는 두 기둥이 같은 위치에 있지 않다는 것도 의미한다). Cody-Jamal은 그중 네 개를 선택하여 각각 $p_{1}$, $p_{2}$, $p_{3}$, $p_{4}$라고 부를 것이다. 그런 다음 $p_{1}$와 $p_{2}$ 사이, $p_{2}$와 $p_{3}$ 사이, $p_{3}$와 $p_{4}$ 사이, 마지막으로 $p_{4}$와 $p_{1}$ 사이에 벨벳 밧줄을 설치할 것이다. 그는 어떤 두 밧줄도 교차하지 않도록 순서가 있는 네 기둥을 선택해야 하며, 이로써 사실상 단순 사각형 $p_{1}$ $p_{2}$ $p_{3}$ $p_{4}$을 형성해야 한다. 이 사각형은 볼록하거나 오목할 수 있다. 그런 다음 그는 밧줄로 구분된 경계 안에 그림을 걸 것이다.

그림을 구매할지도 모르는 부유한 미술 애호가들을 끌어들이기 위해 Cody-Jamal은 방문객들에게 돌아다니며 다과를 제공할 종업원들을 고용한다. 다과 비용은 고정되어 있지만, 종업원 비용은 그들이 걸어야 하는 영역의 넓이에 비례한다. 구체적으로 종업원들은 제곱미터당 2 아트코인을 청구한다. 따라서 Cody-Jamal은 사각형 $p_{1}$ $p_{2}$ $p_{3}$ $p_{4}$의 넓이를 최소화하고, 그에 따라 다과 서비스 비용(아트코인 단위)을 최소화하도록 $p_{1}$, $p_{2}$, $p_{3}$, $p_{4}$을 선택하려고 한다. 가능한 최소 비용은 얼마인가?

제한

메모리 제한: 1GB. -$10^{9}$ ≤ $X_{i}$ ≤ $10^{9}$, 모든 i에 대해. -$10^{9}$ ≤ $Y_{i}$ ≤ $10^{9}$, 모든 i에 대해. 입력의 어떤 세 점도 한 직선 위에 있지 않다.

테스트 세트 1 (Visible Verdict)

시간 제한: 20초. 1 ≤ T ≤ 50. 4 ≤ N ≤ 25.

테스트 세트 2 (Hidden Verdict)

시간 제한: 60초. 1 ≤ T ≤ 30. 4 ≤ N ≤ 1200.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 들판에 있는 기둥의 수를 나타내는 하나의 정수 N이 포함된 줄로 시작한다. 이어서 N개의 줄이 주어지며, 각 줄에는 임의의 원점으로부터 미터 단위로 나타낸 i번째 기둥의 좌표를 나타내는 두 정수 $X_{i}$와 $Y_{i}$가 주어진다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이고(1부터 시작한다), y는 Cody-Jamal이 지불해야 하는 최소 아트코인 수이다. 다시 말해, 입력으로 주어진 점 중 네 개를 꼭짓점으로 하는 가장 작은 단순 사각형 넓이(제곱미터 단위)의 두 배이다.

케이스 #1에서는 입력에 점이 4개뿐이며, 단순 사각형을 형성하도록 선택할 수 있는 순서들은 모두 한 변의 길이가 10인 정사각형을 만든다.

케이스 #2와 #3에서는 첫 번째 점을 제외하고 입력에 주어진 순서대로 마지막 네 점을 사용하는 것이 최적의 선택이다.