시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB10710412.903%

문제

여러분은 골을 넣은 뒤 포효하며 슬라이딩하는 드록바의 모습을 본적이 있는가.

여러분은 이제 동네 축구에서 골을 넣고 드록바처럼 슬라이딩 세레머니를 하려고 한다. 그런데 현실과 이상의 거리는 멀어서 여러분이 뛰는 잔디구장은 드록바가 뛰는 최고급 구장과는 차이가 있다. 여러분의 잔디구장엔 곳곳에 불량한 잔디무더기가 있어서 당신이 슬라이딩을 하다가 그곳을 지나가게 된다면 오랜만에 복귀해서 세레모니하다가 부상당해 찬밥신세가 된 고종수처럼 조기축구회에서 주전자나 나르는 부상자가 될 수도 있다. 그러므로 불량한 잔디무더기는 피해서 세레머니를 하려고 한다.

축구장의 크기와 당신이 골을 넣고 슬라이딩을 시작하는 좌표,  불량 잔디 무더기들(다각형 모양으로 주어진다)가 주어지고 당신의 슬라이딩 경로는 항상 직선이고 축구장 가에서 끝이 나야 할 때 가능한 최장거리의 슬라이딩 경로를 출력하라. 

입력

첫째 줄에는 축구장의 가로, 세로 크기인 N, M(1<=N,M<=10000)이 주어지고 다음 줄엔 당신이 슬라이딩을 시작하는 좌표가 주어진다. 그리고 다음 줄에는 불량잔디 무더기의 개수 G(1<=G<=100)이 주어지고 그 다음 G개의 줄에는 각 불량잔디 무더기의 꼭짓점 수 (20이하)와 그 뒤로 시계방향으로 좌표들이 주어진다.

그리고 세레머니의 시작점이 불량잔디 무더기 안에 포함되는 경우는 없다고 한다. 또한 불량잔디 무더기끼리 겹치는 경우는 없다고 한다. 그리고 세레머니의 경로가 불량잔디 무더기를 통과하지는 않고 접할 경우까지는 괜찮다고 가정한다.

출력

당신이 슬라이딩을 마치는 좌표를 출력한다. 절대/상대 오차는 10-3까지 허용한다. 만약 거리가 같은 최종점이 여러개 존재한다면 그 중 가장 x좌표가 작은 것, x좌표가 같다면 y좌표가 작은 것을 출력하여라.

만약 가능한 슬라이딩 경로가 없다면 GG를 출력하여라.

예제 입력 1

5 4
3 3
2
4 4 1 3 2 4 3 5 2
4 2 1 0 3 2 4 3 4

예제 출력 1

1.500 0.000

출처

  • 문제를 번역한 사람: author4