시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 41 13 11 47.826%

문제

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+XHJcbiIsImhpbnQiOiI8cD4mbmJzcDs8aW1nIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMTA4XC9qai5QTkdcIiBzdHlsZT1cImhlaWdodDoyMDNweDsgd2lkdGg6MjQzcHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjQyOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBvbHlnb24iLCJkZXNjcmlwdGlvbiI6IjxwPkEgc2ltcGxlIHBvbHlnb24gd2l0aCBOIHZlcnRpY2VzIGlzIGRyYXduIG9uIGFuIGluXHVmYjAxbml0ZSByZWN0YW5ndWxhciBncmlkLiBGb3Igc3VjaCBhIHBvbHlnb24sIG9ubHkgbmVpZ2hib3JpbmcgZWRnZXMgdG91Y2ggYXQgdGhlaXIgY29tbW9uIHZlcnRleDsgbm8gb3RoZXIgb2YgaXRzIGVkZ2VzIGludGVyc2VjdCBvciB0b3VjaC4gQWxsIHZlcnRpY2VzIG9mIHRoZSBwb2x5Z29uIGxpZSBvbiBncmlkIHBvaW50cywgaS5lLiwgdmVydGljZXMgaGF2ZSBpbnRlZ2VyIGNvb3JkaW5hdGVzLjxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgdG8gXHVmYjAxbmQgdGhlIHRvdGFsIGxlbmd0aCBvZiBncmlkIGxpbmUgc2VnbWVudHMgd2hpY2ggbGllIHN0cmljdGx5IGluc2lkZSB0aGUgZ2l2ZW4gcG9seWdvbiAodGhlc2UgbGluZSBzZWdtZW50cyBhcmUgaGlnaGxpZ2h0ZWQgaW4gdGhlIGRyYXdpbmdzIGJlbG93KS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIE4sIHRoZSBudW1iZXIgb2YgdmVydGljZXMgb2YgdGhlIHBvbHlnb24uIEVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyB4IGFuZCB5LCB0aGUgY29vcmRpbmF0ZXMgb2Ygb25lIHZlcnRleC4gVGhlIHZlcnRpY2VzIGFyZSBnaXZlbiBlaXRoZXIgaW4gY2xvY2t3aXNlIG9yIGNvdW50ZXJjbG9ja3dpc2Ugb3JkZXIuIEFsbCB2ZXJ0aWNlcyBhcmUgZGlzdGluY3QsIGJ1dCBtb3JlIHRoYW4gdHdvIGNvbnNlY3V0aXZlIHZlcnRpY2VzIG1heSBsaWUgb24gYSBsaW5lLiAoMyAmbGU7IE4gJmxlOyAxMDAsMDAwLCAtNTAwLDAwMCwwMDAgJmxlOyB4LHkgJmxlOyA1MDAsMDAwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gYSBkZWNpbWFsIG51bWJlcjogdGhlIHRvdGFsIGxlbmd0aCBvZiBncmlkIGxpbmUgc2VnbWVudHMgd2hpY2ggbGllIHN0cmljdGx5IGluc2lkZSB0aGUgZ2l2ZW4gcG9seWdvbi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2011 7번