시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB160382022.727%

문제

선영이는 상근이를 만나러 가려고 한다. 두 사람이 사는 곳은 언덕진 곳이다. 선영이는 언덕을 걷는 것을 매우 싫어한다.

선영이는 두 사람이 살고있는 지역의 등고선 지도를 가지고 있다. 지도를 이용해 올라가야 하는 높이의 합과 내려가야 하는 높이의 합을 구해보려고 한다. 이때, 두 값을 최소로 해야 한다.

지도는 xy평면으로 나타낼 수 있고, 선영이의 집은 (0,0), 상근이의 집은 (100 000, 0)에 있다. 등고선은 다각형으로 나타낼 수 있으며, 다각형이 자기 자신이 교차하거나, 다른 다각형과 교차하는 경우는 없다. 또, 선영이와 상근이가 등고선 위에 살고있는 경우는 없다.

위의 그림은 두 번째 예제를 압축해서 그림으로 나타낸 것이다.

입력

첫째 줄에 테스트 케이스의 개수 T (≤ 100)가 주어진다. 각 테스트 케이스의 첫째 줄에는 등고선의 수 0 ≤ N ≤ 2,500 이 주어지며, 다음 줄부터 N개 줄에는 등고선의 정보가 주어진다. 첫 번째 숫자 Hi는 등고선의 높이 (1 ≤ Hi ≤ 1000) 이며, 두 번째 숫자 Pi는 다각형을 이루는 꼭짓점의 개수이다. (3 ≤ Pi ≤ 2000) 다음 숫자는 x1, y1, ..., xPi, yPi로 다각형의 꼭짓점을 나타내며, -300,000 ≤ xi, yi ≤ 300,000 을 만족하는 정수이다.

출력

각 테스트 케이스마다 올라가야 하는 높이의 합과 내려가야 하는 높이의 합을 출력한다.

예제 입력 1

2
2
20 3 10 10 0 -10 -10 10
25 3 20 20 0 -20 -20 20
3
100 4 -1 1 1 1 1 -1 -1 -1
300 8 -2 2 2 2 2 -2 5 -2 5 1 6 1 6 -3 -2 -3
50 8 3 3 100001 3 100001 -1 7 -1 7 2 4 2 4 -1 3 -1

예제 출력 1

5 0
200 250
W3sicHJvYmxlbV9pZCI6IjM3MDAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjNzdcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWI5N2MgXHViOWNjXHViMDk4XHViN2VjIFx1YWMwMFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjMGFjXHViMjk0IFx1YWNmM1x1Yzc0MCBcdWM1YjhcdWIzNTVcdWM5YzQgXHVhY2YzXHVjNzc0XHViMmU0LiBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHVjNWI4XHViMzU1XHVjNzQ0IFx1YWM3N1x1YjI5NCBcdWFjODNcdWM3NDQgXHViOWU0XHVjNmIwIFx1YzJlYlx1YzViNFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjMGI0XHVhY2UwXHVjNzg4XHViMjk0IFx1YzljMFx1YzVlZFx1Yzc1OCBcdWI0ZjFcdWFjZTBcdWMxMjAgXHVjOWMwXHViM2M0XHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzljMFx1YjNjNFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzQgXHVjNjJjXHViNzdjXHVhYzAwXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWIxOTJcdWM3NzRcdWM3NTggXHVkNTY5XHVhY2ZjIFx1YjBiNFx1YjgyNFx1YWMwMFx1YzU3YyBcdWQ1NThcdWIyOTQgXHViMTkyXHVjNzc0XHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NzRcdWJjZjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YjQ1MCBcdWFjMTJcdWM3NDQgXHVjZDVjXHVjMThjXHViODVjIFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzljMFx1YjNjNFx1YjI5NCB4eVx1ZDNjOVx1YmE3NFx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHVjMTIwXHVjNjAxXHVjNzc0XHVjNzU4IFx1YzlkMVx1Yzc0MCAoMCwwKSwgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzlkMVx1Yzc0MCAoMTAwIDAwMCwgMClcdWM1ZDAgXHVjNzg4XHViMmU0LiBcdWI0ZjFcdWFjZTBcdWMxMjBcdWM3NDAgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NzQgXHVjNzkwXHVhZTMwIFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWFkNTBcdWNjMjhcdWQ1NThcdWFjNzBcdWIwOTgsIFx1YjJlNFx1Yjk3OCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWFjZmMgXHVhZDUwXHVjYzI4XHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuIFx1YjYxMCwgXHVjMTIwXHVjNjAxXHVjNzc0XHVjNjQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWI0ZjFcdWFjZTBcdWMxMjAgXHVjNzA0XHVjNWQwIFx1YzBiNFx1YWNlMFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3dhbGsoMikucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTgwcHg7IGxpbmUtaGVpZ2h0OjEuNmVtOyBvcGFjaXR5OjAuOTsgd2lkdGg6MzQ1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzYwOFx1YzgxY1x1Yjk3YyBcdWM1NTVcdWNkOTVcdWQ1NzRcdWMxMWMgXHVhZGY4XHViOWJjXHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFQgKCZsZTsgMTAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNGYxXHVhY2UwXHVjMTIwXHVjNzU4IFx1YzIxOCAwICZsZTsgTiAmbGU7IDIsNTAwIFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWJkODBcdWQxMzAgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNGYxXHVhY2UwXHVjMTIwXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwIEg8c3ViPmk8XC9zdWI+XHViMjk0IFx1YjRmMVx1YWNlMFx1YzEyMFx1Yzc1OCBcdWIxOTJcdWM3NzQgKDEgJmxlOyBIPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMDApIFx1Yzc3NFx1YmE3MCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTAgUDxzdWI+aTxcL3N1Yj5cdWIyOTQgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LiAoMyAmbGU7IFA8c3ViPmk8XC9zdWI+ICZsZTsgMjAwMCkgXHViMmU0XHVjNzRjIFx1YzIyYlx1Yzc5MFx1YjI5NCB4PHN1Yj4xPFwvc3ViPiwgeTxzdWI+MTxcL3N1Yj4sIC4uLiwgeDxzdWI+UDxzdWI+aTxcL3N1Yj48XC9zdWI+LCB5PHN1Yj5QPHN1Yj5pPFwvc3ViPjxcL3N1Yj5cdWI4NWMgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWJhNzAsIC0zMDAsMDAwICZsZTsgeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+ICZsZTsgMzAwLDAwMCBcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWM2MmNcdWI3N2NcdWFjMDBcdWM1N2MgXHVkNTU4XHViMjk0IFx1YjE5Mlx1Yzc3NFx1Yzc1OCBcdWQ1NjlcdWFjZmMgXHViMGI0XHViODI0XHVhYzAwXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWIxOTJcdWM3NzRcdWM3NTggXHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzNzAwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiV2FsayIsImRlc2NyaXB0aW9uIjoiPHA+QWxpY2Ugd291bGQgbGlrZSB0byB2aXNpdCBCb2IuIEhvd2V2ZXIsIHRoZXkgbGl2ZSBpbiBhIGhpbGx5IGxhbmRzY2FwZSwgYW5kIEFsaWNlIGRvZXNuJnJzcXVvO3QgbGlrZSB0byB3YWxrIGluIGhpbGxzLiBTaGUgaGFzIGEgbWFwIG9mIHRoZSBhcmVhLCBzaG93aW5nIHRoZSBoZWlnaHQgY3VydmVzLiBZb3UgaGF2ZSB0byBjYWxjdWxhdGUgdGhlIHRvdGFsIGFsdGl0dWRlIGNsaW1iZWQsIGFuZCB0aGUgdG90YWwgYWx0aXR1ZGUgZGVzY2VuZGVkLCBmb3IgdGhlIHJvdXRlIHdoaWNoIG1pbmltaXplcyB0aGVzZSBudW1iZXJzLiBJdCBkb2VzIG5vdCBtYXR0ZXIgaG93IGZhciBzaGUgaGFzIHRvIHdhbGsgdG8gYWNoaWV2ZSB0aGlzLjxcL3A+XHJcblxyXG48cD5TaW5jZSB5b3UgZG9uJnJzcXVvO3Qga25vdyB3aGF0IHRoZSBsYW5kc2NhcGUgbG9va3MgbGlrZSBpbiBiZXR3ZWVuIHRoZSBoZWlnaHQgY3VydmVzLCB5b3UgY2Fubm90IGtub3cgZXhhY3RseSBob3cgbXVjaCBjbGltYiBhbmQgZGVzY2VudCBzaGUgd2lsbCBhY3R1YWxseSBnZXQgaW4gcHJhY3RpY2UsIGJ1dCB5b3Ugc2hvdWxkIGNhbGN1bGF0ZSB0aGUgbWluaW11bSBwb3NzaWJsZSB1bmRlciBvcHRpbWFsIGNvbmRpdGlvbnMgYmFzZWQgb24gd2hhdCB5b3UgY2FuIGRlZHVjZSBmcm9tIHRoZSBtYXAuPFwvcD5cclxuXHJcbjxwPlRoZSBtYXAgaXMgcmVwcmVzZW50ZWQgYXMgYW4geHkgZ3JpZC4gQWxpY2UgbGl2ZXMgaW4gKDAsIDApLCBhbmQgQm9iIGxpdmVzIGluICgxMDAgMDAwLCAwKS4gVGhlIGhlaWdodCBjdXJ2ZXMgYXJlIHJlcHJlc2VudGVkIGFzIHBvbHlnb25zLCB3aGVyZSBhIHBvbHlnb24gY2Fubm90IGludGVyc2VjdCBpdHNlbGYgb3IgYW5vdGhlciBwb2x5Z29uLiBGdXJ0aGVybW9yZSwgbmVpdGhlciBBbGljZSBub3IgQm9iIGxpdmVzIGV4YWN0bHkgb24gYSBoZWlnaHQgY3VydmUuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvd2FsaygyKS5wbmdcIiBzdHlsZT1cImhlaWdodDoxODBweDsgd2lkdGg6MzQ1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+U2Vjb25kIHRlc3QgY2FzZSBmcm9tIHNhbXBsZSBpbnB1dCAoY29tcHJlc3NlZCkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgXHVmYjAxcnN0IGxpbmUgb25lIHBvc2l0aXZlIG51bWJlcjogdGhlIG51bWJlciBvZiB0ZXN0Y2FzZXMsIGF0IG1vc3QgMTAwLiBBZnRlciB0aGF0IHBlciB0ZXN0Y2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIDAgJmxlOyBOICZsZTsgMiA1MDAsIHRoZSBudW1iZXIgb2YgaGVpZ2h0IGN1cnZlcy48XC9saT5cclxuXHQ8bGk+T25lIGxpbmUgZm9yIGVhY2ggaGVpZ2h0IGN1cnZlLCB3aXRoIDEgJmxlOyBIPHN1Yj5pPFwvc3ViPiAmbGU7IDEgMDAwIGJlaW5nIHRoZSBoZWlnaHQgb2YgdGhlIGN1cnZlLCAzICZsZTsgUDxzdWI+aTxcL3N1Yj4gJmxlOyAyIDAwMCB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIGluIHRoZSBwb2x5Z29uLCBhbmQgdGhlIHZlcnRpY2VzIHg8c3ViPjE8XC9zdWI+LCB5PHN1Yj4xPFwvc3ViPiwgLi4uLCB4PHN1Yj5QPHN1Yj5pPFwvc3ViPjxcL3N1Yj4sIHk8c3ViPlA8c3ViPmk8XC9zdWI+PFwvc3ViPiBoYXZpbmcgaW50ZWdyYWwgdmFsdWVzICZtaW51czszMDAgMDAwICZsZTsgeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+ICZsZTsgMzAwIDAwMC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGVyZSB3aWxsIGJlIG5vIG1vcmUgdGhhbiAyMDAgMDAwIHBvbHlnb24gdmVydGljZXMgaW4gdG90YWwgaW4gYWxsIHRlc3QgY2FzZXMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3RjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggdHdvIG51bWJlcnM6IHRoZSB0b3RhbCBhbHRpdHVkZSBjbGltYmVkIGFuZCB0aGUgdG90YWwgYWx0aXR1ZGUgZGVzY2VuZGVkLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2007 J번