B. 소행성

때는 2115년. 소행성 통신 중계 시스템은 10년 전 소행성 통신부가 구축했다. 시스템은 한 가지 작은 문제만 빼면 잘 돌아가고 있다. 소행성이 너무 많다는 것이다! 작은 소행성들은 중계국의 신호를 계속 방해할 뿐 아니라, 중계국 사이를 오가는 모든 정비 비행선에도 위험하다. 이 작은 소행성들을 파괴해야 한다! 재난 방지를 위한 행성 간 연합(ICPC)이 이 위험한 소행성들의 제거를 맡아, 이 일을 위해 최정예(h\(ot-sh\)ot) 조종사 팀을 고용했다. Han Duo는 이 소행성 파괴 팀의 대장이다. 미사일로 무장한 Han은 소행성대를 누비며 ICPC가 골칫거리로 지목한 소행성을 모조리 날려 버린다. ICPC는 안타까운 예산 문제를 겪고 있다. 그 결과 중 하나로 Han과 그의 팀은 원하는 만큼 미사일을 갖지 못해 골치 아픈 소행성을 전부 날려 버릴 수 없다. 하지만 소행성은 작고 미사일은 강력하다. 그래서 두 소행성이 서로 가까이 있고 적절히 정렬되면 미사일 하나로 둘 다 제거할 수 있다. Han의 화면은 소행성들을 회전하지 않는(n\(on-ro\)tating) 2차원(t\(wo-di\)mensional) 단순 볼록 다각형으로 표시하며, 각각은 일정한 속도로 움직인다. 그는 두 소행성을 맞히기 가장 좋은 때는 두 다각형의 겹치는 부분이 최대일 때라고 판단했다. 예를 들어 샘플 입력 1을 나타낸 그림 B.1은 두 소행성과 1초 간격(\(1-se\)cond)의 이후 위치 스냅숏들을 보여 준다. 두 소행성은 3초 후에 닿기 시작하고 최대 겹침 넓이는 4초와 5초 사이에 나타난다. 그림 B.1: 샘플 입력 1. 경로가 교차하는 두 소행성. 두 소행성의 최대 겹침이 언제 일어나는지 계산하려면 약간의 프로그래밍이 필요한데, 안타깝게도 Han은 비행 학교의 코딩 수업 대부분을 잠으로 보냈다. 여기서 당신이 나설 차례다.

입력은 두 소행성의 명세로 이루어져 있다. 각 명세는 \(n\) \(x_{1}\) \(y_{1}\) \(x_{2}\) \(y_{2}\) . . . \(x_{n}\) \(y_{n}\) \(v_{x}\) \(v_{y}\) 형식이며, \(n\) (\(3 \le n \le 10\))은 꼭짓점의 수이고, 각 \(x_{i}\), y_{i} (−\(10\,000 \le x_{i}\), \(y_{i} \le 10\,000\))는 Han의 화면에 시계 방향 순서로 주어지는 소행성 꼭짓점의 좌표이며, \(vx\), v\(y\) (−\(100 \le vx\), v\(y \le 100\))는 소행성의 \(x\), \(y\) 속도(단위/초, uni\(ts/se\)cond)이다. \(xi\), \(yi\) 값은 시각 \(t = 0\)에서의 각 소행성 위치를 지정하며, 이 시각에 두 다각형은 교차하거나 닿지 않는다. 소행성 한 변의 최대 길이는 500이다. 입력의 모든 수는 정수이다.

두 다각형의 교집합이 최대가 되는 시각(초)을 출력하되, 그런 시각이 여러 개면 가장 이른 것을 출력한다. 두 다각형이 겹치지는 않지만 서로 닿는다면 공통 넓이가 0인 교집합으로 간주하고 그런 가장 이른 시각을 출력한다. 다각형들이 결코 겹치지도 닿지도 않으면 대신 never를 출력한다. 양의 시각만 고려해야 한다. 출력의 절대 또는 상대 오차는 \(10^{−}^{3}\) 이하여야 한다.

생성자가 기록되지 않았습니다.

출처 ICPC World Finals 2015