관악산 정상에는 구름이 없다

시간 제한2초메모리 제한1024 MB

요약
볼록 다각형 밑면과 각 옆면의 이면각이 주어질 때, 두 수평면 H1과 H2 사이에 놓인 뿔 형태 입체의 표면적을 꼭짓점 부분을 제외하고 구한다.
난이도

어려움10점 중 8점

유형
기하, 수학, 구현, 정렬
정답자
아직 제출이 없습니다

문제

관악산 정상에는 구름이 없다.

관악산은 볼록 NN각형 모양 밑면과 NN개의 옆면을 가진 다면체이다. 모든 옆면과 밑면이 이루는 이면각은 예각이다.

관악산 정상은 관악산에서 밑면을 포함하는 평면으로부터 거리가 가장 먼 점들의 집합이다.

구름은 밑면을 포함하는 평면으로부터 거리가 H_1H\_1 이상 H_2H\_2 이하인 영역이다.

관악산의 표면과 구름이 닿는 면적을 구해보자. 단, 관악산 정상에는 구름이 없다.

입력

첫째 줄에 세 정수 NN, H_1H\_1, H_2H\_2가 공백으로 구분되어 주어진다. (3≤N≤105;(3 \le N \le 10^5; 0<H_1<H_2≤108;0 \lt H\_1 \lt H\_2 \le 10^8; 10−3≤H_2−H_1H_1)10^{-3} \le \displaystyle\frac{H\_2 - H\_1}{H\_1})

둘째 줄부터 NN개의 줄에 걸쳐 밑면 꼭짓점 좌표 (x_i,y_i)(x\_i, y\_i)를 나타내는 두 정수 x_ix\_i, y_iy\_i가 공백으로 구분되어 주어진다. 좌표는 반시계 방향 순서로 주어진다. (0≤i<N;(0 \le i \lt N; −108≤x_i,y_i≤108)-10^8 \le x\_i, y\_i \le 10^8)

N+2N+2번째 줄부터 NN개의 줄에 걸쳐 (x_i,y_i)(x\_i, y\_i), (x_i+1,y_i+1)(x\_{i+1}, y\_{i+1})을 지나는 옆면과 밑면이 이루는 이면각 a_i∘a\_i^\circ를 나타내는 정수 a_ia\_i가 주어진다. (x_N,y_N)(x\_N, y\_N)은 (x_0,y_0)(x\_0, y\_0)이다. (0≤i<N;(0 \le i \lt N; 0<a_i<90)0 \lt a\_i \lt 90)

출력

첫째 줄에 관악산의 표면과 구름이 닿는 면적을 출력한다. 절대/상대 오차는 10−610^{-6}까지 허용한다.

힌트

출제자가 관악산 정상에서 직접 찍은 구름 사진이다.

예제4

  1. 예제 1

    입력
    4 2 3
0 0
10 0
10 10
0 10
45
45
45
45
    예상 출력
    28.284271

  2. 예제 2

    입력
    4 3 4
0 0
20 0
20 10
0 10
45
45
45
45
    예상 출력
    45.254834

  3. 예제 3

    입력
    6 1 6
0 0
10 0
15 5
10 10
0 10
-5 5
60
45
45
45
45
45
    예상 출력
    160.878353

  4. 예제 4

    입력
    4 20 30
0 0
10 0
10 10
0 10
45
45
45
45
    예상 출력
    0.000000