About HerdingFrosh ¶
어느 날 대학 캠퍼스 한 가운데 있는 잔디밭을 신입생들이 점령하고 말았다. 캠퍼스 미화를 위해 4학년 선배들이 분홍색 명주실을 써서 신입생들을 감싸기로 했다. 당신은 이 일을 하기 위해 필요한 명주실의 길이를 계산하는 일을 맡게 되었다.
4학년 선배는 전신주에 그 명주실을 묶고, 잔디밭 주변을 한 바퀴 돌면서 명주실로 모든 학생들을 감싼 다음 다시 전신주로 돌아온다. 그 선배는 모든 신입생들을 둘러싸는 필요한 최소 길이만큼의 명주실을 사용했으며, 전신주에 명주실을 묶기 위해서 1미터만 남겼다.
전신주의 위치 좌표는 (0,0) 이라고 하자. 이때 첫번째 좌표는 남/북 방향이고 두번째 좌표는 동/서 방향이다. 신입생의 좌표는 전신주를 기준으로 미터 단위로 주어진다. 신입생 수는 1,000 명을 넘지 않는다.
Input ¶
첫 줄에는 테스트 케이스의 개수를 나타내는 양의 정수 하나가 입력되며, 그 다음 줄은 빈 줄이다.
각 테스트 케이스의 첫 줄에는 신입생 수를 나타내는 정수가 입력되고, 그 밑으로는 n줄에 걸쳐서 각 신입생의 위치를 나타내는 실수가 두 개씩 입력된다.
서로 다른 테스트 케이스 사이에는 빈 줄이 하나씩 입력된다.
각 테스트 케이스의 첫 줄에는 신입생 수를 나타내는 정수가 입력되고, 그 밑으로는 n줄에 걸쳐서 각 신입생의 위치를 나타내는 실수가 두 개씩 입력된다.
서로 다른 테스트 케이스 사이에는 빈 줄이 하나씩 입력된다.
