숲 고속도로

슬로바키아 정부는 Bratislava에서 Košice까지 이어지는 고속도로를 건설하고 있다. 이 고속도로는 많은 동물이 사는 숲을 통과한다. 동물들의 여왕인 Frog Gizela는 고속도로가 동물들의 삶에 미치는 영향을 계산하고자 한다. 고속도로에서는 소음이 발생하므로, 동물들은 고속도로에서 거리 $d$ 이내인 곳에 살고 싶어 하지 않는다. Gizela는 거주 가능한 영역이 얼마나 넓을지 알고 싶다. 숲에서 거주 가능한 영역의 총넓이가 너무 작다면, Gizela는 자신의 왕국을 위한 새로운 숲을 찾아야 한다.

과제

숲과 고속도로에 대한 설명이 주어진다. 숲은 단순 다각형이다. 즉, 그 변들은 서로 교차하지 않으며, 고속도로는 폭이 영인 직선으로 간주할 수 있다. 또한 고속도로로부터의 안전거리인 $d$가 주어진다. 숲에서 거주 가능한 영역의 넓이를 계산한다.

[h]

예제 입력의 그림

입력의 첫째 줄에는 다각형의 정점 수를 나타내는 정수 하나 $N$ $(3\leq N\leq 250\,000)$이 주어진다. 이어지는 $N$개의 줄에는 두 부동소수점 수 $x_i$와 $y_i$가 주어지며, 이는 다각형의 $i$번째 점이 $(x_i, y_i)$임을 나타낸다.

다음 줄에는 부동소수점 수 4개 $x_a, y_a, x_b, y_b$가 주어지며, 고속도로가 점 $(x_a, y_a)$와 $(x_b, y_b)$를 지난다는 것을 나타낸다. 입력의 마지막 줄에는 고속도로로부터의 안전거리인 양의 부동소수점 수 하나 $d$가 주어진다.

모든 부동소수점 수의 절댓값은 최대 $100\,000$이며, 소수점 아래 자릿수는 최대 4개이다.

숲에서 거주 가능한 영역의 넓이를 나타내는 수 하나를 한 줄에 출력한다. 상대 오차 또는 절대 오차가 $10^{-7}$인 결과는 정답으로 간주한다.