시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 164 | 78 | 66 | 49.254% |
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$-좌표축에 평행하며 끝점이 교차하는 두 선분은 수직을 이룬다.
첫 번째 줄에 햇빛을 피할 수 있는 그늘의 길이의 합을 출력한다.
$ N \leq 100, \; 0 \leq x_i, y_i \leq 100 $
추가 제한 없음
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
24
문제 상단에 있는 이미지에 대응하는 입력이다.
6 0 0 0 500000000 -500000000 500000000 -500000000 1000000000 500000000 1000000000 500000000 0
3000000000
Contest > BOJ User Contest > 소프트콘 > 제3회 소프트콘 E번