问题
예술가 Cody-Jamal은 즉흥 야외 갤러리에서 최신 그림을 전시함으로써 힙스터 친구들보다 더 힙해지기로 마음먹었다. 그는 들판에 나타나 그림들을 걸어 전시할 것이다.
들판에는 말뚝이 N개 있고, 그중 어떤 3개를 골라도 한 직선 위에 놓여 있지 않다. (이는 어떤 두 말뚝도 같은 위치에 있지 않다는 것도 의미한다.) Cody-Jamal은 그중 네 개를 고르는데, 이를 p1, p2, p3, p4라고 하자. 그는 p1-p2, p2-p3, p3-p4, 마지막으로 p4-p1 사이에 벨벳 로프를 연결할 것이다. 그는 로프들이 서로 교차하지 않도록 네 말뚝(순서가 있는 선택)을 골라야 하며, 결과적으로 단순 사각형 p1p2p3p4를 형성하게 된다. 이 사각형은 볼록일 수도 오목일 수도 있다. 그런 다음 그는 로프가 둘러싸는 내부에 그림들을 걸어 전시한다.
그림을 구매할 수 있는 부유한 미술 애호가들을 끌어들이기 위해, Cody-Jamal은 관람객에게 다과를 제공할 스태프를 고용한다. 다과 비용은 고정이지만, 스태프 비용은 그들이 걸어 다녀야 하는 면적에 비례한다. 구체적으로 제곱미터당 2 아트코인(artcoin)을 청구한다. 따라서 Cody-Jamal은 사각형 p1p2p3p4의 면적을 최소화하도록 p1, p2, p3, p4를 선택해 다과 서비스 비용(아트코인 단위)을 최소화하고 싶다. 가능한 최소 비용은 얼마인가?
输入
입력의 첫 줄에는 테스트 케이스 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스는 먼저 말뚝의 개수 N이 주어진 한 줄로 시작한다. 이어서 N줄이 주어지며, 각 줄에는 두 정수 Xi, Yi가 주어진다. 이는 임의의 원점을 기준으로 i번째 말뚝의 위치 좌표(미터 단위)를 나타낸다.
输出
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력하라.
여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고,
y는 Cody-Jamal이 지불해야 하는 아트코인의 최소값이다.
다시 말해, 입력 점들 중 4개를 꼭짓점으로 하는 가장 작은 단순 사각형의 면적(제곱미터)의 2배이다.
示例
4
4
-5 5
-5 -5
5 5
5 -5
5
-5 5
-5 -5
5 5
5 -5
4 2
5
-5 5
-5 -4
5 5
5 -5
4 2
4
-1000000000 -1000000000
-1000000000 1000000000
1000000000 -1000000000
1000000000 1000000000
Case #1: 200
Case #2: 30
Case #3: 31
Case #4: 8000000000000000000
需要登录才能编写代码。