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

문제

3차원 공간에 입체도형이 있다. 이 입체도형은 볼록하며, xz평면과 yz평면에 수직으로 빛을 비췄을 때에 나오는 그림자가 볼록다각형 형태를 띤다. 즉, 입체도형의 두 평면에 대한 정사영이 볼록다각형이다. 예를 들어 밑의 그림과 같이 xz평면과 yz평면 위로의 정사영을 각각 Pxz, Pyz라 했을 때 각각이 볼록다각형임을 확인할 수 있다.

우리가 해야 할 일은 위와 같은 입체도형을 xz평면과 yz평면에 정사영시킨 형태가 주어졌을 때에 원본 입체도형을 복원해 그 부피를 구하는 것이다. 하지만 이 정보만으로 입체도형을 유일하게 복원할 수 없기 때문에 가능한 최대 부피를 구해야 한다.

입력

첫째 줄에 xz평면에 비친 정사영의 꼭짓점의 개수 Nxz (3 ≤ Nxz ≤ 1,000)가 주어진다. 그리고 두 번째 줄부터 Nxz+1번째 줄까지 Pxz의 꼭짓점의 좌표 x,z가 시계방향 순서로 공백을 사이에 두고 주어진다. 그리고 Nxz+2번째 줄에는 yz평면에 비친 정사영의 꼭짓점의 개수 Nyz (3 ≤ Nyz ≤ 1,000)가 주어지고 마찬가지로 Nxz+3번째 줄부터 Nxz+Nyz+2번째 줄까지 Pyz의 꼭짓점 좌표 y, z가 시계방향 순서로 공백을 사이에 두고 주어진다.

주어지는 모든 좌표는 절댓값이 500이하이다. 또한 입력되는 두 다각형은 볼록다각형임이 보장되며, 두 다각형의 최소, 최대 z 좌표는 각각 동일하다. 각 다각형의 입력에서 인접한 두 점은 항상 다르지만, 한 변 위에 있는 세 개 이상의 점이 입력될 수는 있다.

출력

첫째 줄에 원본 입체도형의 부피로 가능한 최댓값을 출력한다. 절대/상대 오차는 10-2까지 허용한다.

예제 입력 1

5
1 0
1 -1
-1 0
-1 1
0 1
5
-1 1
0 1
1 1
1 -1
-1 -1

예제 출력 1

5.00
W3sicHJvYmxlbV9pZCI6IjE4NTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTVcdWMwYWNcdWM2MDEiLCJkZXNjcmlwdGlvbiI6IjxwPjNcdWNjMjhcdWM2ZDAgXHVhY2Y1XHVhYzA0XHVjNWQwIFx1Yzc4NVx1Y2NiNFx1YjNjNFx1ZDYxNVx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWM3ODVcdWNjYjRcdWIzYzRcdWQ2MTVcdWM3NDAgXHViY2ZjXHViODVkXHVkNTU4XHViYTcwLCB4elx1ZDNjOVx1YmE3NFx1YWNmYyB5elx1ZDNjOVx1YmE3NFx1YzVkMCBcdWMyMThcdWM5YzFcdWM3M2NcdWI4NWMgXHViZTViXHVjNzQ0IFx1YmU0NFx1Y2RjNFx1Yzc0NCBcdWI1NGNcdWM1ZDAgXHViMDk4XHVjNjI0XHViMjk0IFx1YWRmOFx1YjliY1x1Yzc5MFx1YWMwMCBcdWJjZmNcdWI4NWRcdWIyZTRcdWFjMDFcdWQ2MTUgXHVkNjE1XHVkMGRjXHViOTdjIFx1Yjc2NFx1YjJlNC4gXHVjOTg5LCBcdWM3ODVcdWNjYjRcdWIzYzRcdWQ2MTVcdWM3NTggXHViNDUwIFx1ZDNjOVx1YmE3NFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHVjMGFjXHVjNjAxXHVjNzc0IFx1YmNmY1x1Yjg1ZFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc3NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBcdWJjMTFcdWM3NTggXHVhZGY4XHViOWJjXHVhY2ZjIFx1YWMxOVx1Yzc3NCB4elx1ZDNjOVx1YmE3NFx1YWNmYyB5elx1ZDNjOVx1YmE3NCBcdWM3MDRcdWI4NWNcdWM3NTggXHVjODE1XHVjMGFjXHVjNjAxXHVjNzQ0IFx1YWMwMVx1YWMwMSBQPHN1Yj54ejxcL3N1Yj4sIFA8c3ViPnl6PFwvc3ViPlx1Yjc3YyBcdWQ1ODhcdWM3NDQgXHViNTRjIFx1YWMwMVx1YWMwMVx1Yzc3NCBcdWJjZmNcdWI4NWRcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3ODRcdWM3NDQgXHVkNjU1XHVjNzc4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDZcL1NjcmVlbiBzaG90IDIwMTAtMDYtMTEgYXQgOF80OV8xMCBQTS5wbmdcIiBzdHlsZT1cImhlaWdodDoxODFweDsgd2lkdGg6MzUxcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNmIwXHViOWFjXHVhYzAwIFx1ZDU3NFx1YzU3YyBcdWQ1NjAgXHVjNzdjXHVjNzQwIFx1YzcwNFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjNzg1XHVjY2I0XHViM2M0XHVkNjE1XHVjNzQ0IHh6XHVkM2M5XHViYTc0XHVhY2ZjIHl6XHVkM2M5XHViYTc0XHVjNWQwIFx1YzgxNVx1YzBhY1x1YzYwMVx1YzJkY1x1ZDBhOCBcdWQ2MTVcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0Y1x1YzVkMCBcdWM2ZDBcdWJjZjggXHVjNzg1XHVjY2I0XHViM2M0XHVkNjE1XHVjNzQ0IFx1YmNmNVx1YzZkMFx1ZDU3NCBcdWFkZjggXHViZDgwXHVkNTNjXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWM3NzQgXHVjODE1XHViY2Y0XHViOWNjXHVjNzNjXHViODVjIFx1Yzc4NVx1Y2NiNFx1YjNjNFx1ZDYxNVx1Yzc0NCBcdWM3MjBcdWM3N2NcdWQ1NThcdWFjOGMgXHViY2Y1XHVjNmQwXHVkNTYwIFx1YzIxOCBcdWM1YzZcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWNkNWNcdWIzMDAgXHViZDgwXHVkNTNjXHViOTdjIFx1YWQ2Y1x1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIHh6XHVkM2M5XHViYTc0XHVjNWQwIFx1YmU0NFx1Y2U1YyBcdWM4MTVcdWMwYWNcdWM2MDFcdWM3NTggXHVhZjJkXHVjOWQzXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCBOPHN1Yj54ejxcL3N1Yj4gKDMgJmxlOyBOPHN1Yj54ejxcL3N1Yj4gJmxlOyAxLDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTjxzdWI+eHo8XC9zdWI+KzFcdWJjODhcdWM5ZjggXHVjOTA0XHVhZTRjXHVjOWMwIFA8c3ViPnh6PFwvc3ViPlx1Yzc1OCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NTggXHVjODhjXHVkNDVjIHgselx1YWMwMCBcdWMyZGNcdWFjYzRcdWJjMjlcdWQ1YTUgXHVjMjFjXHVjMTFjXHViODVjIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIE48c3ViPnh6PFwvc3ViPisyXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCB5elx1ZDNjOVx1YmE3NFx1YzVkMCBcdWJlNDRcdWNlNWMgXHVjODE1XHVjMGFjXHVjNjAxXHVjNzU4IFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMTggTjxzdWI+eXo8XC9zdWI+ICgzICZsZTsgTjxzdWI+eXo8XC9zdWI+ICZsZTsgMSwwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCBcdWI5YzhcdWNjMmNcdWFjMDBcdWM5YzBcdWI4NWMgTjxzdWI+eHo8XC9zdWI+KzNcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE48c3ViPnh6PFwvc3ViPitOPHN1Yj55ejxcL3N1Yj4rMlx1YmM4OFx1YzlmOCBcdWM5MDRcdWFlNGNcdWM5YzAgUDxzdWI+eXo8XC9zdWI+XHVjNzU4IFx1YWYyZFx1YzlkM1x1YzgxMCBcdWM4OGNcdWQ0NWMgeSwgelx1YWMwMCBcdWMyZGNcdWFjYzRcdWJjMjlcdWQ1YTUgXHVjMjFjXHVjMTFjXHViODVjIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YmFhOFx1YjRlMCBcdWM4OGNcdWQ0NWNcdWIyOTQgXHVjODA4XHViMzEzXHVhYzEyXHVjNzc0IDUwMFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC4gXHViNjEwXHVkNTVjIFx1Yzc4NVx1YjgyNVx1YjQxOFx1YjI5NCBcdWI0NTAgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzQwIFx1YmNmY1x1Yjg1ZFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc4NFx1Yzc3NCBcdWJjZjRcdWM3YTVcdWI0MThcdWJhNzAsIFx1YjQ1MCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NTggXHVjZDVjXHVjMThjLCBcdWNkNWNcdWIzMDAgeiBcdWM4OGNcdWQ0NWNcdWIyOTQgXHVhYzAxXHVhYzAxIFx1YjNkOVx1Yzc3Y1x1ZDU1OFx1YjJlNC4gXHVhYzAxIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc1OCBcdWM3ODVcdWI4MjVcdWM1ZDBcdWMxMWMgXHVjNzc4XHVjODExXHVkNTVjIFx1YjQ1MCBcdWM4MTBcdWM3NDAgXHVkNTZkXHVjMGMxIFx1YjJlNFx1Yjk3NFx1YzljMFx1YjljYywgXHVkNTVjIFx1YmNjMCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzEzOCBcdWFjMWMgXHVjNzc0XHVjMGMxXHVjNzU4IFx1YzgxMFx1Yzc3NCBcdWM3ODVcdWI4MjVcdWI0MjAgXHVjMjE4XHViMjk0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzZkMFx1YmNmOCBcdWM3ODVcdWNjYjRcdWIzYzRcdWQ2MTVcdWM3NTggXHViZDgwXHVkNTNjXHViODVjIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM4MDhcdWIzMDBcL1x1YzBjMVx1YjMwMCBcdWM2MjRcdWNjMjhcdWIyOTQgMTA8c3VwPi0yPFwvc3VwPlx1YWU0Y1x1YzljMCBcdWQ1YzhcdWM2YTlcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTg1MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ikdlb2RlcyIsImRlc2NyaXB0aW9uIjoiPHA+SW4gdGhlIG1vdW50YWlucyBvZiBHZW9kZXNpYSwgZ2VvZGVzIGFyZSBmb3VuZC4gVGhlc2UgJiMzOTtob2xsb3cmIzM5OyBzdG9uZXMgY29udGFpbiBjYXZpdGllcyB3aXRoIGNyeXN0YWwgZm9ybWF0aW9ucyBhcm91bmQgdGhlbS4gVGhlIGJlYXV0aWZ1bGx5IGNvbG9yZWQgY3J5c3RhbHMgY2FuIGJlIHNvbGQgZm9yIGEgaGlnaCBwcmljZSB0byBwZW9wbGUgYm90aCBpbnNpZGUgYW5kIG91dHNpZGUgb2YgR2VvZGVzaWEuIFRoZSBwcm9ibGVtIHdpdGggZ2VvZGVzIGlzIHRoYXQgb25lIGNhbm5vdCBzZWUgZnJvbSB0aGUgb3V0c2lkZSBvZiBhIGdpdmVuIHJvY2sgd2hldGhlciBpdCBpcyBhIGdlb2RlIG9yIG5vdC4gT3V0IG9mIGV2ZXJ5IHRob3VzYW5kIHJvY2tzIGZvdW5kIGluIEdlb2Rlc2lhIG9ubHkgc29tZSBhcmUgZ2VvZGVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiBvcmRlciB0byBmaW5kIG91dCB3aGV0aGVyIGEgZ2l2ZW4gcm9jayBpcyBpbiBmYWN0IGEgZ2VvZGUsIG9uZSBjYW4gdHJ5IHRvIGNvbnNpZGVyIGl0cyBkZW5zaXR5Jm5ic3A7PFwvcD5cclxuXHJcbjxwPlxcW1xccmhvID1cXGZyYWN7bX17Vn1cXF08XC9wPlxyXG5cclxuPHA+d2hlcmUgbSByZXByZXNlbnRzIGl0cyBtYXNzIGFuZCBWIGl0cyB2b2x1bWUuIFNpbmNlIGEgZ2VvZGUgY29udGFpbnMgZW1wdHkgc3BhY2UsIGEgcm9jayBjb250YW5pbmcgb25lIGlzIGV4cGVjdGVkIHRvIGhhdmUgYSBsb3dlciBkZW5zaXR5IHRoYW4gb3RoZXIgcm9ja3MuIElmIHRoZSBkZW5zaXR5IG9mIGEgcm9jayBpcyB0b28gaGlnaCwgaXQgd291bGQgYmUgYSB3YXN0ZSBvZiB0aW1lIGFuZCBlZmZvcnQgdG8gZnVydGhlciBpbnZlc3RpZ2F0ZSBpdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QnV0IGhvdyBjb3VsZCBvbmUgZGV0ZXJtaW5lIHRoZSBkZW5zaXR5IG9mIGVhY2ggb2YgdGhlIGVub3Jtb3VzIG51bWJlciBvZiByb2NrcyBmb3VuZCBpbiB0aGUgbW91bnRhaW5zIG9mIEdlb2Rlc2lhPyBNaW5pZyBjcmFmdHMgY29sbGVjdCByb2Nrcywgd2hpY2ggdGhleSBwdXQgb24gbW9iaWxlIGNvbnZleWVyIGJlbHRzLiBXZWlnaGluZyB0aGUgcm9ja3MgYXV0b21hdGljYWxseSBhdCBhIGZhc3QgcmF0ZSBpcyBubyBwcm9ibGVtLCBidXQgaG93IHRvIHF1aWNrbHkgZGV0ZXJtaW5lIHRoZWlyIHZvbHVtZT8gTWVhc3VyaW5nIGUuZy4gdGhlIHZvbHVtZSBkaXNwbGFjZW1lbnQgb2YgYSBsaXF1aWQobGlrZSBIMk8pLCB3aGVyZSBlYWNoIHJvY2sgaGFzIHRvIGJlIHB1dCBpbiBhbmQgdGFrZW4gb3V0IGluZGl2aWR1YWxseSBpcyBhIHRpbWUgY29uc3VtaW5nIHByb2Nlc3MuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlNvIHdoeSBub3QgdHJ5IHRvIGVzdGltYXRlIHRoZSB2b2x1bWUganVzdCBieSBsb29raW5nIGF0IHRoZSByb2NrPyBBbG9uZyB0aGUgY29udmV5ZXIgYmVsdCwgdHdvIGNhbWVyYXMgYXJlIHBsYWNlZCwgcGVycGVuZGljdWxhciB0byBlYWNoIG90aGVyLiBPZiBldmVyeSByb2NrIHRoYXQgcGFzc2VzLCB0aGV5IGVhY2ggdGFrZSBhIHBpY3R1cmUuIFRoZXNlIHBpY3R1cmVzIGFyZSBzZW50IHRvIGEgY29tcHV0ZXIgZm9yIHByb2Nlc3NpbmcuIFRoZSBjb21wdXRlciBjYWxjdWxhdGVzIGZyb20gdGhlc2UgcGljdHVyZXMgYW4gdXBwZXIgYm91bmQgZm9yIHRoZSB2b2x1bWUgb2YgdGhlIHJvY2ssIFZtYXguIEEgbG93ZXIgYm91bmQgZm9yIHRoZSBkZW5zaXR5IG9mIHRoZSByb2NrIGlzIHRoZW4gZ2l2ZW4gYnkmbmJzcDs8XC9wPlxyXG5cclxuPHA+XFxbXFxyaG9fe21pbn0gPVxcZnJhY3ttfXtWX3ttYXh9fSBcXGxlIFxcZnJhY3ttfXtWfT1cXHJoby5cXF08XC9wPlxyXG5cclxuPHA+VGhpcyBsb3dlciBib3VuZCBjYW4gdGhlbiBiZSB1c2VkIHRvIHJlamVjdCByb2NrcyB0aGF0IGFyZSBjZXJ0YWlubHkgdG9vIGhlYXZ5IHRvIGJlIGdlb2Rlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGNvbXB1dGVyIHVzZXMgYSByZWxhdGl2ZWx5IHNpbXBsZSB0cmljayBmb3IgZXN0aW1hdGluZyB0aGUgbWF4aW1hbCB2b2x1bWUuIEl0IGNvbnNpZGVycyB0aGUgcGljdXJlcyB0YWtlbiBhcyBzaWxob3VldHRlcywgYXMgcGFyYWxsZWwgcHJvamVjdGlvbnMgb2YgYSByb2NrIG9udG8gYSBwbGFuZXMuIFNpbmNlIHRoZSB0d28gY2FtZXJhcyBhcmUgcGxhY2VkIHBlcnBlbmRpY3VsYXIgdG8gZWFjaCBvdGhlciwgdGhlIHByb2plY3Rpb24gcGxhbmVzIGFyZSBhbHNvIHBlcnBlbmRpY3VsYXIgdG8gZWFjaCBvdGhlci4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SW4gb3RoZXIgd29yZHMsIGNob29zZSBhIGNvb3JkaW5hdGUgc3lzdGVtIGluIHRocmVlIGRpbWVuc2lvbmFsIHNwYWNlIGFzIGZvbGxvd3M6IHogcnVucyBhbG9uZyB0aGUgdmVydGljYWwgZGlyZWN0aW9uIGFuZCB4IGFuZCB5IHJ1biBhbG9uZyB0aGUgcGVycGVuZGljdWxhciBob3Jpem9udGFsIGRpcmVjdGlvbnMgaW4gd2hpY2ggdGhlIHR3byBjYW1lcmFzIGFyZSBwbGFjZWQuIExldCBTICZpc2luOyBSPHN1cD4zPFwvc3VwPiByZXByZXNlbnQgYSByb2NrLiBUaGVuIHRoZSBjYW1lcmFzIHlpZWxkIHRoZSB0d28gcGFyYWxsZWwgcHJvamVjdGlvbnMmbmJzcDs8XC9wPlxyXG5cclxuPHA+XFxbUF97eHp9ID1cXGxlZnRcXHsgKHgseikgOiAoeCx5LHopIFxcaW4gUyB+Zm9yIH5zb21lfnkgXFxpbiBcXG1hdGhiYntSfSAmbmJzcDtcXHJpZ2h0XFx9ICZuYnNwO35hbmQmbmJzcDs8YnIgXC8+XHJcblBfe3l6fSA9XFxsZWZ0XFx7ICh5LHopIDogKHgseSx6KSBcXGluIFMgfmZvciB+c29tZX54IFxcaW4gXFxtYXRoYmJ7Un0gJm5ic3A7XFxyaWdodFxcfSBcXF08XC9wPlxyXG5cclxuPHA+b24gdGhlIHh6IGFuZCB5eiBwbGFuZSByZXNwZWN0aXZlbHkuIFNlZSBGaWd1cmUgMSBmb3IgYW4gZXhhbXBsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm93IGEgY3VyaW91cyBwcm9wZXJ0eSBvZiB0aGUgcm9ja3MgZm91bmQgaW4gR2VvZGVzaWEgbWFrZXMgdGhlIG1lYXN1cmVtZW50IG9mIHRoZSB2b2x1bWUgZWFzaWVyOiB0aGV5IGFyZSBhbGwgY29udmV4MS4gRnVydGhlcm1vcmUsIHRoZSBwcm9qZWN0aW9ucyBjYW4gYmUgY29uc2lkZXJlZCBhcyBwb2x5Z29ucy4gU28gZmlyc3QgZWFjaCBvZiB0aGUgdHdvIHBpY3R1cmVzIHRha2VuIG9mIGEgcm9jayBpcyBjb252ZXJ0ZWQgaW50byBhIGNvbnZleCBwb2x5Z29uIGJ5IGFuIGltYWdlIHJlY29nbml0aW9uIHByb2dyYW0uIFlvdSBhcmUgdG8gd3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBkbyB0aGUgc2Vjb25kIHN0ZXA6IGNvbXB1dGUgZnJvbSB0aGVzZSB0d28gcG9seWdvbnMgVm1heDogdGhlIG1heGltdW0gdm9sdW1lIG9mIGFueSByb2NrIGhhdmluZyBleGFjdGx5IHRoZXNlIHR3byBwb2x5Z29uLXNoYXBlZCBwcm9qZWN0aW9ucy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIG51bWJlcjogdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIHRvIGZvbGxvdy4gRWFjaCB0ZXN0IGNhc2UgaGFzIHRoZSBmb2xsb3dpbmcgZm9ybWF0OiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2dlb2RlcygxKS5wbmdcIiBzdHlsZT1cImhlaWdodDoyMzhweDsgd2lkdGg6MzQ2cHhcIiBcLz48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIHRoZSBpbnRlZ2VyIG48c3ViPnh6PFwvc3ViPiB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIGRlc2NyaWJpbmcgdGhlIHByb2plY3Rpb24gb24gdGhlIHh6IHBsYW5lLjxcL2xpPlxyXG5cdDxsaT5uPHN1Yj54ejxcL3N1Yj4gbGluZXMsIGVhY2ggd2l0aCB0d28gaW50ZWdlcnMgeCBhbmQgeiwgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlOiB0aGUgY29vcmRpbmF0ZXMgb2Ygb25lIHZlcnRleCBvZiB0aGUgeHogcHJvamVjdGlvbi48XC9saT5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCB0aGUgaW50ZWdlciBuPHN1Yj55ejxcL3N1Yj4sIHRoZSBudW1iZXIgb2YgdmVydGljZXMgZGVzY3JpYmluZyB0aGUgcHJvamVjdGlvbiBvbiB0aGUgeXogcGxhbmUuPFwvbGk+XHJcblx0PGxpPm48c3ViPnl6PFwvc3ViPiBsaW5lcywgZWFjaCB3aXRoIHR3byBpbnRlZ2VycyB5IGFuZCB6LCBzZXBlcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2U6IHRoZSBjb29yZGluYXRlcyBvZiBvbmUgdmVydGV4IG9mIHRoZSB5eiBwcm9qZWN0aW9uLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkJvdGggcHJvamVjdGlvbnMgYXJlIGNvbnZleCBwb2x5Z29ucywgYW5kIHRoZSBtaW5pbXVtIGFuZCBtYXhpbXVtIHogY29vcmRpbmF0ZXMgYXJlIHRoZSBzYW1lIHZhbHVlcy4gVGhlIHZlcnRpY2VzIG9mIHRoZSBwb2x5Z29ucyBhcmUgZ2l2ZW4gaW4gY2xvY2t3aXNlIG9yZGVyLiBDb25zZWN1dGl2ZSB2ZXJ0aWNlcyBvZiB0aGUgcG9seWdvbnMgYXJlIGRpZmZlcmVudCwgYnV0IHRoZXJlIG1heSBiZSB0aHJlZSBvciBtb3JlIGNvbnNlY3V0aXZlIHZlcnRpY2VzIG9uIG9uZSBsaW5lLiBUaGUgbnVtYmVycyBpbiB0aGUgaW5wdXQgc2F0aXNmeSAzICZsZTsgbjxzdWI+eHo8XC9zdWI+LCBuPHN1Yj55ejxcL3N1Yj4gJmxlOyAxMDAwLCBhbmQgfHh8LCB8eXwsIHx6fCAmbGU7IDUwMC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZXZlcnkgdGVzdCBjYXNlIGluIHRoZSBpbnB1dCwgdGhlIG91dHB1dCBzaG91bGQgY29udGFpbiBhIHNpbmdsZSBudW1iZXIgb24gYSBzaW5nbGUgbGluZTogVjxzdWI+bWF4PFwvc3ViPiwgdGhlIG1heGltdW0gdm9sdW1lIG9mIGFueSBvYmplY3QgaGF2aW5nIHRoZSBwcm9qZWN0aW9ucyBnaXZlbiBpbiB0aGUgaW5wdXQsIHJvdW5kZWQgaW4gdGhlIHVzdWFsIHdheSB0byB0d28gZGVjaW1hbHMgYmVoaW5kIHRoZSBkZWNpbWFsIHBvaW50LCBBIHJvdW5kLW9mZiBlcnJvciBvZiAwLjAxIGlzIHBlcm1pdHRlZCBpbiB5b3VyIGFuc3dlci4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2006 A번

  • 데이터를 추가한 사람: gratus907
  • 문제를 다시 작성한 사람: tlwpdus