시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 46 17 9 50.000%

문제

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

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

입력

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

출력

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

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

예제 입력 1

3
5 1
2 4
1 1

예제 출력 1

10.0

힌트

 

W3sicHJvYmxlbV9pZCI6IjI0MjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFlMzhcdWM3NzQiLCJkZXNjcmlwdGlvbiI6IjxwPk5cdWFjMWNcdWM3NTggXHVhZjJkXHVjOWQzXHVjODEwXHVjNzQ0IFx1YWMwMFx1YzljNCBcdWIyZThcdWMyMWMgXHViMmU0XHVhYzAxXHVkNjE1IChTaW1wbGUgUG9seWdvbilcdWM3NzQgXHViYjM0XHVkNTVjXHVkNTVjIFx1YzBhY1x1YWMwMSBcdWFjYTlcdWM3OTBcdWQzMTBcdWM1ZDAgXHVhZGY4XHViODI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViMmU4XHVjMjFjIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc0MCwgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViY2MwXHVjNzc0IFx1YzYyNFx1YzljMSBcdWQ1NThcdWIwOThcdWM3NTggXHVhY2Y1XHVkMWI1XHViNDFjIFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc0NCBcdWM5YzBcdWIwOThcdWFjZTAsIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWJjYzBcdWM3NzQgXHVjNTQ0XHViMmM4XHViNzdjXHViYTc0IFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YWM3MFx1YjA5OCwgXHVjODExXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc0MCBcdWM4MTVcdWMyMTggXHVjODhjXHVkNDVjXHViOTdjIFx1YWMwMFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViN2VjXHVkNTVjIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzQsIFx1YjJlNFx1YWMwMVx1ZDYxNSBcdWIwYjRcdWJkODBcdWM1ZDAgXHVhY2E5XHVjNzkwIFx1YzEyMFx1YmQ4NFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVhZDZjXHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC4gKFx1YWRmOFx1YjliYyBcdWNjMzhcdWFjZTApPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOCB4XHVjNjQwIHlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVjODhjXHVkNDVjXHViMjk0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NzRcdWIyZTQuIFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc0MCBcdWMyZGNcdWFjYzRcdWJjMjlcdWQ1YTUgXHViNjEwXHViMjk0IFx1YmMxOFx1YzJkY1x1YWNjNCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWJhYThcdWI0ZTAgXHVhZjJkXHVjOWQzXHVjODEwXHVjNzQwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzRcdWIyZTQuICgzJmx0Oz1OJmx0Oz0xMDAsMDAwLCAtNTAwLDAwMCwwMDAmbHQ7PXgseSZsdDs9NTAwLDAwMCwwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCwgXHViMmU0XHVhYzAxXHVkNjE1IFx1YjBiNFx1YmQ4MFx1Yzc1OCBcdWFjYTlcdWM3OTAgXHVjMTIwXHViZDg0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4MTVcdWIyZjVcdWFjZmNcdWM3NTggXHVjODA4XHViMzAwXC9cdWMwYzFcdWIzMDAgXHVjNjI0XHVjYzI4XHViMjk0IDEwPHN1cD4tMzxcL3N1cD5cdWFlNGNcdWM5YzAgXHVkNWM4XHVjNmE5XHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD4mbmJzcDs8aW1nIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMTA4XC9qai5QTkdcIiBzdHlsZT1cImhlaWdodDoyMDNweDsgd2lkdGg6MjQzcHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI0MjkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQb2x5Z29uIiwiZGVzY3JpcHRpb24iOiI8cD5BIHNpbXBsZSBwb2x5Z29uIHdpdGggTiB2ZXJ0aWNlcyBpcyBkcmF3biBvbiBhbiBpblx1ZmIwMW5pdGUgcmVjdGFuZ3VsYXIgZ3JpZC4gRm9yIHN1Y2ggYSBwb2x5Z29uLCBvbmx5IG5laWdoYm9yaW5nIGVkZ2VzIHRvdWNoIGF0IHRoZWlyIGNvbW1vbiB2ZXJ0ZXg7IG5vIG90aGVyIG9mIGl0cyBlZGdlcyBpbnRlcnNlY3Qgb3IgdG91Y2guIEFsbCB2ZXJ0aWNlcyBvZiB0aGUgcG9seWdvbiBsaWUgb24gZ3JpZCBwb2ludHMsIGkuZS4sIHZlcnRpY2VzIGhhdmUgaW50ZWdlciBjb29yZGluYXRlcy48XC9wPlxyXG5cclxuPHA+WW91ciB0YXNrIGlzIHRvIFx1ZmIwMW5kIHRoZSB0b3RhbCBsZW5ndGggb2YgZ3JpZCBsaW5lIHNlZ21lbnRzIHdoaWNoIGxpZSBzdHJpY3RseSBpbnNpZGUgdGhlIGdpdmVuIHBvbHlnb24gKHRoZXNlIGxpbmUgc2VnbWVudHMgYXJlIGhpZ2hsaWdodGVkIGluIHRoZSBkcmF3aW5ncyBiZWxvdykuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBOLCB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIG9mIHRoZSBwb2x5Z29uLiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMgeCBhbmQgeSwgdGhlIGNvb3JkaW5hdGVzIG9mIG9uZSB2ZXJ0ZXguIFRoZSB2ZXJ0aWNlcyBhcmUgZ2l2ZW4gZWl0aGVyIGluIGNsb2Nrd2lzZSBvciBjb3VudGVyY2xvY2t3aXNlIG9yZGVyLiBBbGwgdmVydGljZXMgYXJlIGRpc3RpbmN0LCBidXQgbW9yZSB0aGFuIHR3byBjb25zZWN1dGl2ZSB2ZXJ0aWNlcyBtYXkgbGllIG9uIGEgbGluZS4gKDMgJmxlOyBOICZsZTsgMTAwLDAwMCwgLTUwMCwwMDAsMDAwICZsZTsgeCx5ICZsZTsgNTAwLDAwMCwwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIGEgZGVjaW1hbCBudW1iZXI6IHRoZSB0b3RhbCBsZW5ndGggb2YgZ3JpZCBsaW5lIHNlZ21lbnRzIHdoaWNoIGxpZSBzdHJpY3RseSBpbnNpZGUgdGhlIGdpdmVuIHBvbHlnb24uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2011 7번