로미엣과 줄리오

문제 정보

문제

로미엣과 줄리오는 비극의 주인공답게 항상 서로를 그리워 한다.

그들이 서로를 그리워 하는 이유는 수학적(?)으로 간단하다.



1. 가까이에 있다.

2. 하지만 만날 수가 없다.



소설가 rainpunch는 로미엣과 줄리오를 주인공으로 새로운 비극을 하나 쓰려고 한다.

그녀가 새로 쓸 비극에는 여러 섬이 등장하는데, 로미엣과 줄리오의 집을 서로 다른 섬에 배치할 생각이다.

그래야 그 둘이 쉽게 만날 수 없을 테고, 그래야 서로를 그리워 할 테니까.



그리고 그들을 최대한 더 그립게 하기 위해서 그들의 집을 최대한 가깝게 배치하기로 결정했다.

rainpunch를 위해 로미엣과 줄리오의 집을 배치해 주자.

입력

첫째 줄에는 테스트 케이스의 개수 T가 주어진다. (T <= 40)

각 테스트 케이스의 첫째 줄에는 섬의 개수를 의미하는 정수 n이 주어진다. (2 <= n <= 100)

다음 n개의 줄에 1번 섬부터 n번 섬까지 각각의 섬에 대한 정보가 주어진다.

섬에 대한 정보는 우선 i번 섬을 이루고 있는 꼭지점의 개수 mi (1<= i <= n, 3 <= mi <= 20)가 주어지고,

그 뒤에 mi개의 2차원 좌표가 주어진다. 좌표는 0 이상, 10000 이하의 소수점 둘째자리 실수로 표현된다.

좌표를 순서대로 이으면 볼록다각형이 된다. 각 섬은 서로 겹치지 않으며, 섬이 아닌 곳은 전부 바다다.

출력

각 테스트 케이스에 대해서 첫번째 줄에 로미엣과 줄리오의 집이 배치될 두 섬의 번호를 오름차순으로 출력하고, 두번재 줄에 로미엣과 줄리오의 집 사이 거리를 출력한다.

거리는 소수점 3번째 자리에서 반올림한다.

답이 여러개인 경우는 없다.

예제 입력

2
2
4
0.00 0.00
0.00 1.00
1.00 1.00
1.00 0.00
4
3.00 0.00
4.00 1.00
3.00 2.00
2.00 1.00
3
3
6.00 0.00
8.00 0.00
6.00 2.00
4
1.00 0.00
2.00 1.00
1.00 2.00
0.00 1.00
4
4.00 0.00
5.00 1.00
1.00 5.00
0.00 4.00

예제 출력

1 2
1.00
2 3
0.71

노트

0개의 댓글이 있습니다.