돔

성 바실리 대성당은 모스크바를 대표하는 명소이며, 어쩌면 러시아 전체에서 가장 잘 알려진 건축물이다. 16세기 이반 뇌제의 명으로 지어진 이 성당은 화려한 색의 돔으로 유명하다. 붉은 광장에서 이 옛 성당의 사진을 찍지 않고서는 도시를 제대로 구경했다고 할 수 없다.

그림 C.1: 성 바실리 대성당을 두 방향에서 본 모습.

모스크바 관광청(MTB)은 관광객이 성당의 완벽한 사진을 안전하게 찍을 수 있도록 만들고 싶다. 사진을 찍을 때 어디에 서 있느냐에 따라 돔들의 상대적 위치가 달라진다(그림 C.1 참조). MTB는 일부 원하는 돔 배열에 대해 사진을 찍을 수 있는 붉은 광장 안의 영역이 너무 좁아져 사진사들이 위험할 정도로 밀집할 수 있다고 우려한다. 밀치고 다치는 사고와 코로나 감염을 피하기 위해, MTB는 원하는 돔 순서마다 사진을 찍을 수 있는 영역의 넓이를 구하려 한다.

그림 C.2: 예제 입력의 도해.

간단히 하기 위해 카메라의 화각은 180도라고 가정한다. 그림 C.2에는 평면 위의 돔 위치(1번부터 5번)와 사진사(초록 점)가 나와 있다. 사진사가 카메라를 왼쪽으로, 즉 5번 돔을 향해 똑바로 두고 찍으면 음영 처리된 영역 안의 모든 것이 사진에 담긴다. 이 사진에서 돔들은 왼쪽에서 오른쪽으로 4, 3, 5, 2, 1 순서로 나타난다.

붉은 광장 안 돔들의 위치와 사진에서 원하는 돔의 왼쪽에서 오른쪽 순서가 주어질 때, MTB는 그러한 사진을 찍을 수 있는 붉은 광장 안 영역의 넓이를 알고 싶어 한다. 돔은 점으로 가정하므로 사진사의 시야에서 일직선 위에 있지 않은 한 서로를 가리지 않는다.

첫째 줄에 세 정수 dx, dy, n이 주어진다. dx와 dy(2 ≤ dx, dy ≤ 105)는 붉은 광장의 크기이고, n(1 ≤ n ≤ 100)은 돔의 개수이다. 붉은 광장의 왼쪽 아래 모서리는 원점 (0, 0)에, 오른쪽 위 모서리는 좌표 (dx, dy)에 있다.

다음 n개 줄에는 각각 두 정수 xi와 yi(0 < xi < dx, 0 < yi < dy)가 주어지며, 돔의 위치 (xi, yi)를 나타낸다. i번째 줄은 i번 돔을 나타낸다. 두 돔이 같은 위치에 있는 경우는 없다.

마지막 줄에는 사진에서 원하는 돔의 왼쪽에서 오른쪽 순서를 나타내는 {1, ..., n}의 순열이 주어진다.

요청한 순서로 돔이 보이는 사진을 찍을 수 있는 붉은 광장 안 영역의 넓이를 출력한다. 요청한 사진을 찍을 수 있는 위치가 없으면 넓이는 0일 수 있다. 답의 절대 오차 또는 상대 오차는 10−3 이하여야 한다.