걷기
시간 제한1초메모리 제한128 MB
서로 교차하지 않는 등고선 폴리곤들이 주어질 때, 두 고정된 점을 잇는 경로에서 오를 높이의 합과 내려갈 높이의 합을 최소로 만드는 값을 각 점을 둘러싄 폴리곤 정보로 구하는 문제입니다.
문제
선영이는 상근이를 만나러 가려고 한다. 두 사람이 사는 곳은 언덕이 많은 지역이고, 선영이는 언덕을 오르내리는 것을 매우 싫어한다.
선영이는 두 사람이 사는 지역의 등고선 지도를 가지고 있다. 이 지도를 이용해, 상근이의 집까지 걸어가는 동안 올라가야 하는 높이의 합과 내려가야 하는 높이의 합을 구하려고 한다. 이때 두 값을 모두 최소로 만들어야 한다.
지도는 xy평면으로 나타낸다. 선영이의 집은 (0, 0)에, 상근이의 집은 (100000, 0)에 있다. 각 등고선은 다각형으로 주어지며, 어떤 다각형도 자기 자신과 교차하거나 다른 다각형과 교차하지 않는다. 또한 선영이와 상근이의 집은 어떤 등고선 위에도 놓여 있지 않는다.
입력
첫째 줄에 테스트 케이스의 개수 T (T ≤ 100)가 주어진다.
각 테스트 케이스의 첫째 줄에는 등고선의 개수 N (0 ≤ N ≤ 2500)이 주어진다. 이어지는 N개의 줄에는 각 등고선의 정보가 한 줄에 하나씩 주어진다. 각 줄의 첫 번째 정수 Hi는 등고선의 높이 (1 ≤ Hi ≤ 1000), 두 번째 정수 Pi는 다각형을 이루는 꼭짓점의 개수 (3 ≤ Pi ≤ 2000)이다. 그 뒤에 꼭짓점의 좌표가 x1, y1, x2, y2, …, xPi, yPi 순서로 주어지며, 모든 좌표는 -300000 ≤ xi, yi ≤ 300000을 만족하는 정수이다.
출력
각 테스트 케이스마다 올라가야 하는 높이의 합과 내려가야 하는 높이의 합을 공백 하나로 구분하여 한 줄에 출력한다.