파이몬 다각형

파이몬이 평면 위에 서로 다른 $(n+1)$개의 점을 찍는다. 그중 하나는 특별한 점 $O=(0,0)$이고, 나머지 점들의 집합을 $\mathbb{S}$라고 한다.

점 집합 $\mathbb{U}$가 엄격한 볼록 집합(strict convex set)이라는 것은 $|\mathbb{U}| \ge 3$이고, $\mathbb{U}$의 모든 점이 $\mathbb{U}$로 만든 볼록 껍질 위에 정확히 놓이며, 세 점이 한 직선 위에 있지 않은 경우를 말한다.

$\mathbb{S}$를 두 집합 $\mathbb{A}$와 $\mathbb{B}$로 나누어 다음 조건을 만족하게 하라.

• $\mathbb{A} \cap \mathbb{B}=\emptyset$
• $\mathbb{A} \cup \mathbb{B}=\mathbb{S}$
• $|\mathbb{A}| \ge 2, |\mathbb{B}| \ge 2$
• $\mathbb{A} \cup \{O\}$는 엄격한 볼록 집합이다. 그 볼록 껍질을 $C_{\mathbb{A} \cup \{O\}}$라고 한다.
• $\mathbb{B} \cup \{O\}$는 엄격한 볼록 집합이다. 그 볼록 껍질을 $C_{\mathbb{B} \cup \{O\}}$라고 한다.
• $C_{\mathbb{A} \cup \{O\}}$의 변과 $C_{\mathbb{B} \cup \{O\}}$의 변은 $O$에서만 만난다. 즉 두 변 모두에 놓이는 점은 $O$ 하나뿐이다.

두 볼록 껍질의 둘레 길이 합이 최대가 되도록 나누어라. 즉 $(L(C_{\mathbb{A} \cup \{O\}}) + L(C_{\mathbb{B} \cup \{O\}}))$를 최대로 하는 유효한 분할 $\mathbb{A}$, $\mathbb{B}$를 구하라. 여기서 $L(\text{polygon})$은 해당 다각형의 둘레이다.

테스트 케이스는 여러 개이다. 첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

첫 줄에 $\mathbb{S}$의 점 개수 $n$ ($4 \le n \le 5 \times 10^5$)이 주어진다.

이어지는 $n$개의 줄에는 각각 두 정수 $x_i$, $y_i$ ($-10^9 \le x_i, y_i \le 10^9$, $(x_i, y_i) \ne (0, 0)$)가 주어지며, 이는 $\mathbb{S}$의 $i$번째 점의 좌표이다.

한 테스트 케이스 안의 점들은 서로 다르다. 같은 직선 위에 세 점 이상이 놓일 수 있다. 모든 테스트 케이스의 $n$을 합한 값은 $10^6$을 넘지 않는다.

각 테스트 케이스마다 둘레 길이 합의 최댓값을 한 줄에 출력한다. 유효한 분할이 없으면 "0"(따옴표 제외)을 출력한다. 상대 오차 또는 절대 오차가 $10^{-6}$ 미만이면 정답으로 인정한다.

그림은 첫 번째 예시 입력에 대해 유효한 분할(왼쪽)과 유효하지 않은 분할(오른쪽)을 보여준다.