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

문제

N개의 꼭짓점을 가진 단순 다각형 (Simple Polygon)이 무한한 사각 격자판에 그려져 있다. 단순 다각형은, 두 개의 인접한 변이 오직 하나의 공통된 꼭짓점을 지나고, 이러한 변이 아니라면 교차하거나, 접하지 않는다. 모든 꼭짓점은 정수 좌표를 가진다.

이러한 다각형이 주어지면, 다각형 내부에 격자 선분의 길이를 구하면 된다.

입력

첫째 줄에 꼭짓점의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 두 정수 x와 y가 주어진다. 이 좌표는 하나의 꼭짓점이다. 꼭짓점은 시계방향 또는 반시계 방향으로 주어지며, 모든 꼭짓점은 서로 다르다.

출력

첫째 줄에, 다각형 내부의 격자 선분의 길이를 출력하면 된다.

정답과의 절대/상대 오차는 10-6까지 허용된다.

제한

  • 3 ≤ N ≤ 100 000
  • −500 000 000 ≤ x, y ≤ 500 000 000

예제 입력 1

3
5 1
2 4
1 1

예제 출력 1

10.0

예제 입력 2

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

예제 출력 2

12.5

W3sicHJvYmxlbV9pZCI6IjI0MjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFlMzhcdWM3NzQiLCJkZXNjcmlwdGlvbiI6IjxwPk5cdWFjMWNcdWM3NTggXHVhZjJkXHVjOWQzXHVjODEwXHVjNzQ0IFx1YWMwMFx1YzljNCBcdWIyZThcdWMyMWMgXHViMmU0XHVhYzAxXHVkNjE1IChTaW1wbGUgUG9seWdvbilcdWM3NzQgXHViYjM0XHVkNTVjXHVkNTVjIFx1YzBhY1x1YWMwMSBcdWFjYTlcdWM3OTBcdWQzMTBcdWM1ZDAgXHVhZGY4XHViODI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViMmU4XHVjMjFjIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc0MCwgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViY2MwXHVjNzc0IFx1YzYyNFx1YzljMSBcdWQ1NThcdWIwOThcdWM3NTggXHVhY2Y1XHVkMWI1XHViNDFjIFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc0NCBcdWM5YzBcdWIwOThcdWFjZTAsIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWJjYzBcdWM3NzQgXHVjNTQ0XHViMmM4XHViNzdjXHViYTc0IFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YWM3MFx1YjA5OCwgXHVjODExXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc0MCBcdWM4MTVcdWMyMTggXHVjODhjXHVkNDVjXHViOTdjIFx1YWMwMFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViN2VjXHVkNTVjIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzQsIFx1YjJlNFx1YWMwMVx1ZDYxNSBcdWIwYjRcdWJkODBcdWM1ZDAgXHVhY2E5XHVjNzkwIFx1YzEyMFx1YmQ4NFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVhZDZjXHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhZjJkXHVjOWQzXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI0NTAgXHVjODE1XHVjMjE4IHhcdWM2NDAgeVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWM4OGNcdWQ0NWNcdWIyOTQgXHVkNTU4XHViMDk4XHVjNzU4IFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc3NFx1YjJlNC4gXHVhZjJkXHVjOWQzXHVjODEwXHVjNzQwIFx1YzJkY1x1YWNjNFx1YmMyOVx1ZDVhNSBcdWI2MTBcdWIyOTQgXHViYzE4XHVjMmRjXHVhY2M0IFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YmFhOFx1YjRlMCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwLCBcdWIyZTRcdWFjMDFcdWQ2MTUgXHViMGI0XHViZDgwXHVjNzU4IFx1YWNhOVx1Yzc5MCBcdWMxMjBcdWJkODRcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzgxNVx1YjJmNVx1YWNmY1x1Yzc1OCBcdWM4MDhcdWIzMDBcL1x1YzBjMVx1YjMwMCBcdWM2MjRcdWNjMjhcdWIyOTQgMTA8c3VwPi02PFwvc3VwPlx1YWU0Y1x1YzljMCBcdWQ1YzhcdWM2YTlcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjMgJmxlOyBOICZsZTsgMTAwIDAwMDxcL2xpPlxyXG5cdDxsaT4mbWludXM7NTAwIDAwMCAwMDAgJmxlOyB4LCB5ICZsZTsgNTAwIDAwMCAwMDA8XC9saT5cclxuPFwvdWw+XHJcbiIsInNhbXBsZV9leHBsYWluXzEiOiI8cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzgwZDk0ZGY5LWZiOTEtNGQ1ZC1hODkxLTBiMWEyMzQ3NDFmM1wvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMjM4cHg7IGhlaWdodDogMjAwcHg7XCIgXC8+PFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMiI6IjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvNDg3NTE0ZTctOTJkOC00NGQ4LTk2MTMtZDVmOWJiZDMyNGUxXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAyMzhweDsgaGVpZ2h0OiAyMzhweDtcIiBcLz48XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiIyNDI5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUG9seWdvbiIsImRlc2NyaXB0aW9uIjoiPHA+QSBzaW1wbGUgcG9seWdvbiB3aXRoIE4gdmVydGljZXMgaXMgZHJhd24gb24gYW4gaW5cdWZiMDFuaXRlIHJlY3Rhbmd1bGFyIGdyaWQuIEZvciBzdWNoIGEgcG9seWdvbiwgb25seSBuZWlnaGJvcmluZyBlZGdlcyB0b3VjaCBhdCB0aGVpciBjb21tb24gdmVydGV4OyBubyBvdGhlciBvZiBpdHMgZWRnZXMgaW50ZXJzZWN0IG9yIHRvdWNoLiBBbGwgdmVydGljZXMgb2YgdGhlIHBvbHlnb24gbGllIG9uIGdyaWQgcG9pbnRzLCBpLmUuLCB2ZXJ0aWNlcyBoYXZlIGludGVnZXIgY29vcmRpbmF0ZXMuPFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byBcdWZiMDFuZCB0aGUgdG90YWwgbGVuZ3RoIG9mIGdyaWQgbGluZSBzZWdtZW50cyB3aGljaCBsaWUgc3RyaWN0bHkgaW5zaWRlIHRoZSBnaXZlbiBwb2x5Z29uICh0aGVzZSBsaW5lIHNlZ21lbnRzIGFyZSBoaWdobGlnaHRlZCBpbiB0aGUgZHJhd2luZ3MgYmVsb3cpLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgTiwgdGhlIG51bWJlciBvZiB2ZXJ0aWNlcyBvZiB0aGUgcG9seWdvbi4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzIHggYW5kIHksIHRoZSBjb29yZGluYXRlcyBvZiBvbmUgdmVydGV4LiBUaGUgdmVydGljZXMgYXJlIGdpdmVuIGVpdGhlciBpbiBjbG9ja3dpc2Ugb3IgY291bnRlcmNsb2Nrd2lzZSBvcmRlci4gQWxsIHZlcnRpY2VzIGFyZSBkaXN0aW5jdCwgYnV0IG1vcmUgdGhhbiB0d28gY29uc2VjdXRpdmUgdmVydGljZXMgbWF5IGxpZSBvbiBhIGxpbmUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIGEgZGVjaW1hbCBudW1iZXI6IHRoZSB0b3RhbCBsZW5ndGggb2YgZ3JpZCBsaW5lIHNlZ21lbnRzIHdoaWNoIGxpZSBzdHJpY3RseSBpbnNpZGUgdGhlIGdpdmVuIHBvbHlnb24uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4zICZsZTsgTiAmbGU7IDEwMCAwMDA8XC9saT5cclxuXHQ8bGk+Jm1pbnVzOzUwMCAwMDAgMDAwICZsZTsgeCwgeSAmbGU7IDUwMCAwMDAgMDAwPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC84MGQ5NGRmOS1mYjkxLTRkNWQtYTg5MS0wYjFhMjM0NzQxZjNcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDIzOHB4OyBoZWlnaHQ6IDIwMHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5UaGUgbGVuZ3RoIG9mIGhvcml6b250YWwgbGluZXMgaXMgNFwvMyArIDhcLzMgPSA0LiBUaGUgbGVuZ3RoIG9mIHZlcnRpY2FsIGxpbmVzIGlzIDMgKyAyICsgMSA9IDYuPFwvcD5cclxuXHJcbjxwPlRoZSB0b3RhbCBsZW5ndGggaXMgNCArIDYgPSAxMC48XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8yIjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC80ODc1MTRlNy05MmQ4LTQ0ZDgtOTYxMy1kNWY5YmJkMzI0ZTFcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwiaGVpZ2h0OiAyMzhweDsgd2lkdGg6IDIzOHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5UaGUgbGVuZ3RoIG9mIGhvcml6b250YWwgbGluZXMgaXMgMSArIDIgKyA0ID0gNy4gVGhlIGxlbmd0aCBvZiB2ZXJ0aWNhbCBsaW5lcyBpcyA5XC80ICsgM1wvMiArIDdcLzQgPSA1LjUuPFwvcD5cclxuXHJcbjxwPlRoZSB0b3RhbCBsZW5ndGggaXMgNyArIDUuNSA9IDEyLjUuPFwvcD5cclxuIn1d

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2011 7번