골 세레모니
시간 제한2초메모리 제한128 MB
장애물 다각형이 있는 직사각형 필드에서 시작점으로부터 내부를 통과하지 않는 직선 경로로 갈 수 있는 가장 먼 경계점을 찾는 문제입니다.
문제
가로 길이가 N, 세로 길이가 M인 직사각형 축구장이 있다. 한 선수가 좌표 (x, y)에서 골 세레모니로 슬라이딩을 시작하려고 한다.
축구장 곳곳에는 불량 잔디 구역이 있으며, 각 구역은 다각형으로 주어진다. 슬라이딩 경로는 시작점에서 축구장 경계의 한 점까지 이어지는 하나의 직선이어야 한다. 경로가 불량 잔디 구역의 내부를 지나가면 안 되지만, 구역의 경계나 꼭짓점에 닿기만 하는 것은 허용된다.
가능한 슬라이딩 경로 중 길이가 가장 긴 경로의 끝점을 구하라.
입력
첫째 줄에 축구장의 가로 길이와 세로 길이 N, M이 주어진다. (1 <= N, M <= 10000)
둘째 줄에 슬라이딩을 시작하는 좌표가 주어진다.
셋째 줄에 불량 잔디 구역의 개수 G가 주어진다. (1 <= G <= 100)
다음 G개의 줄에는 각 구역의 꼭짓점 수가 먼저 주어지고, 이어서 그 꼭짓점들의 좌표가 시계 방향 순서로 주어진다. 한 구역의 꼭짓점 수는 20 이하이다.
시작점은 어떤 불량 잔디 구역의 내부에도 포함되지 않는다. 불량 잔디 구역끼리는 서로 겹치지 않는다.
출력
슬라이딩을 마치는 좌표를 출력한다. 절대 오차 또는 상대 오차가 10^-3 이하이면 정답으로 인정된다.
최대 거리가 같은 끝점이 여러 개라면 x좌표가 가장 작은 끝점을 출력한다. 그래도 여러 개라면 y좌표가 가장 작은 끝점을 출력한다.
가능한 슬라이딩 경로가 없다면 GG를 출력한다.