최후의 방어선
면접 대비시간 제한3초메모리 제한512 MB
최대 5개의 다각형이 만드는 가스 농도 변화를 고려하여, 생성 지점에서 시설까지 이동할 때의 최소 피해를 구합니다.
문제
빈번하게 미확인 생물의 침략을 받게 된 어느 나라는 중요 시설을 신형 방어 병기로 보호하기로 했다. 이 병기는 다각형 영역에 특수한 가스를 채워 미확인 생물에게 피해를 줄 수 있다. 미확인 생물이 이동하는 도중에 가스 농도가 바뀌면, 두 농도 차이의 절댓값만큼 피해를 입는다. 가스 농도가 같은 영역을 지나는 동안에는 피해가 전혀 발생하지 않는다.
현재 기술로는 가스 농도를 일정한 값으로만 설정할 수 있으므로, 이 나라는 병기를 여러 대 투입하기로 했다. 모든 병기의 가스 농도는 같으며, 여러 병기의 영역이 겹치는 부분에서는 농도가 더해진다.
미확인 생물의 출현 지점과 중요 시설의 위치가 주어졌을 때, 출현 지점에서 시설까지 이동하는 동안 받는 피해의 최솟값을 구하라. 이동 경로에는 다각형의 꼭짓점이나 다각형끼리의 교점이 포함되지 않는다. 또한 미확인 생물이 다각형의 변을 따라 이동하는 일은 없다.
입력
입력은 다음 형식으로 주어진다.
다각형의 수
다각형의 꼭짓점 수
x좌표 y좌표
x좌표 y좌표
...
다각형의 꼭짓점 수
x좌표 y좌표
x좌표 y좌표
...
출현 지점과 중요 시설 데이터의 수
출현 지점 x좌표 출현 지점 y좌표 중요 시설 x좌표 중요 시설 y좌표
출현 지점 x좌표 출현 지점 y좌표 중요 시설 x좌표 중요 시설 y좌표
...
출력
출현 지점과 중요 시설의 쌍마다, 미확인 생물이 시설까지 이동하면서 받는 피해의 최솟값을 한 줄에 하나씩 출력하라.
제한
- 입력에 포함된 좌표는 절댓값이 1,000 이하인 정수이다.
- 다각형의 수는 1 이상 5 이하이다.
- 다각형의 꼭짓점 수는 3 이상 5 이하이다.
- 출현 지점과 중요 시설 데이터의 수는 1 이상 100 이하이다.
- 다각형은 주어진 꼭짓점을 순서대로 이은 도형이며, 자기 교차는 없다.
- 출현 지점과 중요 시설은 다각형의 꼭짓점이나 변 위에 있지 않다.