프로그램 명: boi_polygon(special judge)
제한시간: 1 초
단순 다각형(simple polygon)이란 연속 한 두 변 이외에는 어떤 두 변도 교차하지 않는 다각형이다.
단순 다각형이 주어질 때 내부의 라인세그먼트의 총 길이의 합을 구하는 것이다.(그림에서 굵은 선)
꼭지점은 정수 좌표로 주어진다.
A simple polygon with N vertices is drawn on an infinite rectangular grid. For such a polygon, only
neighboring edges touch at their common vertex; no other of its edges intersect or touch. All vertices
of the polygon lie on grid points, i.e., vertices have integer coordinates.
Your task is to find the total length of grid line segments which lie strictly inside the given polygon
(these line segments are highlighted in the drawings below).
입력
-
The first line of input contains a single integer N, the number of vertices of the polygon.
- Each of the following N lines contains two integers x and y, the coordinates of one vertex. The vertices are given
either in clockwise or counterclockwise order. All vertices are distinct, but more than two consecutive
vertices may lie on a line.
출력
The only line of output must contain a decimal number: the total length of grid line segments which
lie strictly inside the given polygon.
제한
-
3 <= N <= 100 000
-
-500 000 000 <= x,y <= 500 000 000
In test cases worth 50 points, all polygon edges lie on grid lines.
Grading
Your output is graded correct if it is close enough to the expected output.
To be more precise: Let your output number be L, and let the expected result be R. Then, at least one
of the two following conditions must hold:
-
| L-R | <= R * 10 ^ -6 (relative precision)
-
| L-R | <= 10 ^ -6 ( absolute precision )
입출력 예
입력
3
5 1
2 4
1 1
출력
10.0
The length of horizontal lines is 4/3 + 8/3 = 4. The length of vertical lines is 3 + 2 + 1 = 6.
The total length is 4 + 6 = 10.
입력
5
0 0
-2 2
-2 -1
2 -2
2 0
출력
12.5
The length of horizontal lines is 1 + 2 + 4 = 7. The length of vertical lines is 9/4 + 3/2 + 7/4 = 5.5.
The total length is 7 + 5.5 = 12.5.
출처:boi 2011
[질/답]
[제출 현황]
[푼 후(0)]