시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 79 27 25 37.879%

문제

2차원 세계에 직각다각형 형태의 조형물이 하나있다. 즉, 조형물의 표면은 $x$-좌표축 또는 $y$-좌표축에 평행하다.

태양은 매우 멀리있기에 거리와 위치에 상관없이 빛이 항상 오른쪽 상단에서 왼쪽 하단으로 45도로 입사한다.

달팽이는 매우 작아 점으로 표현할 수 있다. 달팽이는 조형물 표면(천장 벽 포함) 또는 땅 $(y = 0)$ 에 붙어다니는데 일부는 빛을 받지 못하여 그늘이 생기는 곳이 있다.

달팽이는 그늘에서 햇빛을 피하고 싶다. 달팽이를 위해 달팽이가 햇빛을 피할 수 있는 그늘의 총 길이를 구하자. 

입력

첫 번째 줄에 조형물의 꼭짓점의 개수 $N$ ($4 \leq N \leq 200,000$) 이 주어진다.

다음 $N$ 개 줄에는 각 줄에 조형물의 꼭짓점들의 좌표 ($x_i$, $y_i$) ($-10^9 \leq x_i \leq 10^9$, $0 \leq y_i \leq 10^9$) 가 차례대로 주어진다. 주어지는 꼭짓점들의 순서는 시계방향이며 $i \; (1 \leq i < N)$ 번째 점과 $i+1$ 번째 점을 이은 선분이 하나의 표면을 이룬다.

$y_1$과 $y_N$은 항상 $0$ 이고 나머지 $y_i$ 는 $0$보다 크다. 그리고 $x_1 \lt x_N$ 를 만족한다.

표면을 나타내는 선분들은 끝점을 제외하고 서로 교차하지 않고 $x$-좌표축 또는 $y$-좌표축에 평행하며 끝점이 교차하는 두 선분은 수직을 이룬다.

출력

첫 번째 줄에 햇빛을 피할 수 있는 그늘의 길이의 합을 출력한다.

서브태스크 1 (64점)

$ N \leq 100, \; 0 \leq x_i, y_i \leq 100 $

서브태스크 2 (61점)

추가 제한 없음

예제 입력 1

12
-8 0
-8 3
-5 3
-5 2
-2 2
-2 7
6 7
6 5
2 5
2 2
8 2
8 0

예제 출력 1

24

문제 상단에 있는 이미지에 대응하는 입력이다.

예제 입력 2

6
0 0
0 500000000
-500000000 500000000
-500000000 1000000000
500000000 1000000000
500000000 0

예제 출력 2

3000000000

출처

Contest > 소프트콘 > 제3회 소프트콘 E번

채점 및 기타 정보

  • 예제는 채점하지 않는다.