2429번 - 길이 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 67 | 27 | 23 | 48.936% |
문제
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
출처
Olympiad > Baltic Olympiad in Informatics > BOI 2011 7번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호