이고리와 장난감

일주일 내내 비가 그치지 않자 이고리는 집에서 좋아하는 장난감만 가지고 놀았다. 하지만 같은 놀이를 오래 하니 금방 지겨워져서, 이고리는 부모님께 새 장난감을 사 달라고 졸랐다. 부모님은 쉽게 허락했고, 다음 날 온 가족이 장난감 가게로 갔다.

가게에 들어서자 이고리의 눈이 휘둥그레졌다. 레이싱카, 흰 돛이 달린 배, 반짝이는 날이 눈길을 끄는 검까지 모두 갖고 싶었다. 가게에는 새 장난감이 모두 $N$개 있고, 모두 평평하며 볼록 다각형 모양이다. 가게 이름이 '어린이를 위한 십만 하나의 볼록 다각형'인 것을 생각하면 당연하다. 엄격한 아버지는 이고리에게 장난감을 두 개만 사 주겠다고 했다. 이고리는 머릿속으로 조합을 따져 보았지만 경우의 수가 너무 많았다. 정확히는 장난감 쌍을 고르는 방법이 $Q$가지인 경우의 답이 궁금했다.

이고리는 장난감을 포장하는 방식이 궁금해졌다. 각 쌍 $i$, $j$에 대해 이고리는 다음 작업을 한다. 처음에 각 장난감은 몸에 꼭 맞는 평평한 직사각형 상자에 들어 있다. 이고리는 두 상자를 탁자 위에 나란히 놓는데, $i$번 장난감을 $j$번 장난감의 왼쪽에 놓아도 되고 오른쪽에 놓아도 된다. 그다음 상자를 치우고 장난감을 가능한 한 서로 바싹 붙인 뒤, 그 결과물을 다시 상자에 넣는다(그림 참고). 이고리는 알뜰해서 최종 상자의 크기를 알고 싶어 한다. 장난감은 탁자 면과 평행하게만 밀 수 있으므로 높이는 바뀌지 않는다. 따라서 최종 상자의 최소 너비만 구하면 된다.

장난감은 탁자 면과 평행하게만 움직일 수 있고 어떤 방식으로도 회전할 수 없다. 그러므로 문제는 2차원으로 볼 수 있다. $Ox$축은 탁자 면 위에 있고, 높이를 재는 $Oy$축은 탁자 면에 수직이다. 상자의 변은 좌표축과 평행하다. 가게의 장난감 중에는 탁자 위에 세워 둘 수 있는 것도 있으며, 꼭짓점 하나만 대고 균형을 잡을 수도 있다.

첫 줄에는 장난감의 개수를 나타내는 자연수 $N$($1 \le N \le 100000$)이 주어진다. 그다음에는 $N$개의 볼록 다각형이 차례로 주어진다. $m$번째 다각형은 먼저 꼭짓점 개수 $k_m$($3 \le k_m \le 300000$)이 주어지고, 이어서 $k_m$개의 줄에 정수 쌍 $x_{m,s}$, $y_{m,s}$가 한 줄에 하나씩 주어진다. 모든 좌표의 절댓값은 $10^9$을 넘지 않는다. 꼭짓점은 반시계 방향 순서로 주어지며, 각 장난감을 담은 상자의 좌표계에서 표현된다. 즉 $y_{m,s} > 0$이고, 모든 장난감에는 $y_{m,v_m} = 0$인 꼭짓점 $v_m$이 있다. 모든 $k_m$의 합을 $S$라 하면 $S \le 300000$이다.

그다음 줄에는 질의 개수를 나타내는 자연수 $Q$($1 \le Q \le 500000$)가 주어진다. 이어서 $Q$개의 줄에 자연수 쌍 $i_t$, $j_t$($1 \le i_t < j_t \le N$)가 한 줄에 하나씩 주어지며, 이는 그 질의에서 밀어 맞출 장난감의 번호다.

$Q$개의 줄에 각 질의의 답을 출력한다. 각 줄에는 필요한 상자의 최소 너비를 나타내는 실수 하나를 출력한다. 절대 오차 또는 상대 오차가 $10^{-9}$ 이하이면 정답으로 인정한다.

위쪽 그림은 장난감이 상자에 들어 있던 처음 상태를 보여 준다. 아래 그림은 장난감을 밀어 맞춘 최종 배치의 예시이며, 왼쪽이 최적 배치다.