케이크 자르기

이코와 피코는 ACM 박사가 개발한 인공지능을 탑재한 쌍둥이 로봇이다. 오늘은 두 사람의 생일이라서 박사는 딸기가 많이 올려진 케이크를 준비했다.

케이크는 가로 W × 세로 H 인 직사각형 모양이다. 편의상 케이크는 위에서 보았을 때 (0,0), (W,0), (W,H), (0,H)를 꼭짓점으로 하는 직사각형이 되도록 놓여 있다고 하자. 또한 두 사람이 똑같이 나눠 먹을 수 있도록 정확히 2N 개의 딸기가 올려져 있다.

기왕이면 박사는 두 사람에게 케이크를 자르게 하기로 했다. 이코와 피코는 힘을 합쳐 케이크를 자르기 때문에, 이코가 칼의 한쪽 끝을 변 (0,0)-(0,H) 위에 놓고 피코는 다른 쪽 끝을 변 (W,0)-(W,H) 위에 놓은 다음 동시에 아래로 내리는 방법을 쓰기로 했다. 물론 칼은 직선이므로 선택한 두 점을 지나는 직선으로 케이크가 둘로 나뉜다. (그림 E-1)

그림 E-1

박사는 인공지능을 완성한 것에 만족하고 나머지 부분은 대충 만들어서 두 사람의 팔 부품이 불안정해졌다. 그래서 변 (0,0)-(0,H) (또는 변 (W,0)-(W,H)) 위의 원하는 위치에 놓으려 해도 어쩔 수 없이 어긋나 버린다.

두 사람은 딸기를 좋아하기 때문에 가능하면 N 개씩 나누고 싶어 한다. 그래서 N 개씩 나눠지도록 자를 수 없으면 두 점을 다시 고르기로 했다. 2N 개의 딸기 배치에 따라서는 반씩 나눌 수 없을 수도 있고, 나눌 수 있더라도 확률이 아주 낮을 수도 있다. 이런 경우에 두 점을 여러 번 다시 고르는 것은 헛된 일이므로, 먼저 N 개씩 나눠지도록 자를 수 있는 확률을 계산하기로 했다.

두 사람의 팔 부품이 불안정하기 때문에 움직임을 예측하기 어렵다. 우선 두 사람은 "칼을 놓는 점은 반드시 변 (0,0)-(0,H) (또는 변 (W,0)-(W,H)) 위에 있고, 놓이는 확률은 어느 두 점이든 같다"라는 가정을 두기로 했다. 또 딸기의 크기를 고려하는 것도 번거로우므로 점으로 보기로 했다.

이는 인공지능의 성능을 시험할 좋은 기회이다. 박사와 같은 연구소에서 일하는 당신에게, 2N 개의 딸기 위치가 주어졌을 때 두 사람과 같은 가정을 사용해 딸기가 N 개씩 나뉠 확률을 계산하는 프로그램을 만드는 일이 맡겨졌다.

입력은 여러 데이터 세트로 이루어진다. 입력의 끝은 공백으로 구분된 세 개의 0으로 이루어진 줄로 주어진다. 각 데이터 세트는 케이크 하나에 대한 정보를 나타내며, 형식은 다음과 같다.

W H N
x1 y1
...
x2N y2N

데이터 세트의 첫 줄은 세 개의 정수 W, H, N 으로 이루어지며, 각각 케이크의 가로, 세로, 딸기 개수/2를 나타낸다. 이어지는 2N 개의 줄은 두 개의 정수로 이루어지며, 각각 딸기의 x좌표와 y좌표를 나타낸다.

각 값은 다음 조건을 만족한다.

• 1 ≤ W, H ≤ 1,000
• 1 ≤ N ≤ 100
• 0 ≤ xi ≤ W
• 0 ≤ yi ≤ H

또한 서로 다른 두 딸기가 같은 좌표에 있는 경우는 없다.

각 데이터 세트에 대해 두 사람의 가정을 사용했을 때 딸기가 2등분될 확률을 나타내는 실수를 한 줄에 출력하라. 답에는 10-8 을 넘는 오차가 있어서는 안 된다. 그 외의 불필요한 문자를 출력해서는 안 된다.