무게중심
시간 제한2초메모리 제한512 MB
A, B 타일의 질량을 주어진 범위에서 무작위로 뽑을 때 그물 무게중심이 빈 칸에 떨어질 확률을 구합니다.
문제
여러 개의 정사각형 타일로 저글링을 연습하고 있다. 타일은 모두 크기가 같아 보이지만 사실 A, B, X 세 종류가 있다. 타일의 종류는 질량으로 구별할 수 있다. 같은 종류의 타일은 질량이 정확히 같다. A 종류 타일의 질량은 [mA1, mA2] 범위에 있다. B 종류 타일의 질량도 마찬가지로 [mB1, mB2] 범위에 있다. A와 B의 정확한 질량은 알지 못한다. X 종류 타일의 질량은 정확히 mX이다.
타일로 이루어진 큰 물체를 하나 얻었다. 타일은 H × W 격자에 배치되어 있다. 인접한 모든 타일은 모서리에서 붙어 있다. H × W 격자의 일부 칸은 비어 있을 수 있다.
이 물체를 막대 위에서 균형 잡으려고 했다. 그러다 물체의 무게중심이 궁금해졌다. 무게중심이 빈 칸 위에 있으면 물체를 막대 위에 올릴 수 없다. 정사각형 타일 하나의 무게중심은 정사각형의 중심이다. 질량이 m1과 m2인 두 물체를 합친 물체의 무게중심은 두 중심을 잇는 선분을 m2 : m1의 비로 내분하는 점이다.
큰 물체의 무게중심이 물체 위에, 즉 구멍 위가 아닌 곳에 있을 확률을 계산하는 프로그램을 작성하라. A와 B 타일의 정확한 질량은 알 수 없지만, 확률은 위에서 언급한 범위의 연속 균등분포를 따른다. 분포는 A와 B 사이에서 독립이라고 가정할 수 있다.
입력
입력은 다음과 같은 형식이다.
H W
mA1 mA2 mB1 mB2 mX
M1,1M1,2...M1,W
M2,1M2,2...M2,W
:
:
MH,1MH,2...MH,W
입력의 첫 줄에는 공백으로 구분된 두 정수 H와 W (1 ≤ H, W ≤ 50)가 주어진다. H와 W는 주어진 행렬의 행과 열의 개수이다.
입력의 둘째 줄에는 공백으로 구분된 다섯 정수 mA1, mA2, mB1, mB2, mX (1 ≤ mA1 < mA2 ≤ 100, 1 ≤ mB1 < mB2 ≤ 100, 1 ≤ mX ≤ 100)가 주어진다.
다음 H개의 줄은 각각 W개의 문자로 이루어져 있으며 주어진 행렬을 나타낸다. 이 H개의 줄에서 A, B, X는 각각 A 종류, B 종류, X 종류 타일 한 개를 나타내고, .은 타일이 놓이지 않은 빈 칸을 나타낸다. 이 H개의 줄에는 다른 문자가 없다.
i번째 행 j번째 열의 칸은 왼쪽 위 모서리의 좌표가 (i, j)이고 오른쪽 아래 모서리의 좌표가 (i+1, j+1)이다.
주어진 행렬에는 A, B, X가 각각 적어도 하나씩 있고, 모든 타일은 적어도 한 변에서 연결되어 있다고 가정할 수 있다. 또한 물체의 무게중심의 x좌표가 정수일 확률은 0이고, 무게중심의 y좌표가 정수일 확률도 0이라고 가정할 수 있다.
출력
물체의 무게중심이 물체 위에 있을 확률을 출력한다. 출력의 오차는 10-8을 넘지 않아야 한다.