워터월드

최근 몇 년 사이 태양계 밖에서 수천 개의 행성이 발견되었다. 생명체가 살 가능성을 따질 때 중요한 요소는 액체 상태의 물이 있는지 여부이다. 먼 행성에서 물을 찾아내는 일은 쉽지 않다. 자전하는 행성의 경우, 상대론적 양자 편광 분광법이라는 새로운 기술이 도움이 될 수 있다. 동작 방식은 다음과 같다 (이 설명은 단순화한 것이며, 이 행성에서 실제 원리를 아는 사람은 세 명뿐이다).

망원경은 자전축이 세로, 적도가 가로에 놓이도록 행성을 보여 준다고 가정한다. 영상 가운데의 세로선(자전축을 지나는 선)만 분석한다. 이 선이 행성 표면의 해상도를 가장 높게 제공하기 때문이다.

분석은 $d$도 단위로 진행된다. 한 단계에서는 행성이 $d$도 회전하는 동안 데이터를 모으므로, 각 단계는 행성 표면의 $d$도 폭 조각에 대한 정보를 준다. 영상은 높이가 같은 $n$개의 구간으로 나뉘어 각각 따로 분석된다. 따라서 $d$도 폭 조각은 $n$개의 영역 $A_1,\dots ,A_n$으로 나뉜다. 영상 분석은 각 영역 $A_i$에서 물로 덮인 비율(%)을 하나의 수로 내놓는다. 한 단계의 영역 $A_i$는 오른쪽 그림에 표시되어 있다.

행성 표면은 구라고 가정해도 된다. 따라서 $A_2,\dots ,A_{n-1}$의 각 영역은 구면 위의 사각형이다. 꼭짓점은 네 개이고, 변은 두 쌍이다. 한 쌍은 적도와 평행한 변으로, 적도 평면과 평행한 평면 위에 놓인다. 다른 한 쌍은 두 극을 지나는 대원 위의 변으로, 두 대원의 간격은 $d$도이다. 양 극에서는 꼭짓점 두 개가 극으로 모이므로, $A_1$과 $A_n$은 적도와 평행한 변이 하나뿐인 구면 삼각형이다. 표면의 곡률 때문에, 적도와 평행한 변은 적도에 가까울수록 길고, 대원 위의 변은 극에 가까울수록 길다.

위 과정을 다음 $d$도 회전에 대해 반복하고, 이를 총 $m$번 한다. 행성 표면 전체를 덮으면 끝난다($md=360$도). 주어진 데이터로부터 물로 덮인 행성 표면의 비율을 구하라.

첫 줄에 두 정수 $n$과 $m$이 주어진다($2\le n,m\le 1000$). 이어지는 $n$개의 줄에는 각각 $m$개의 정수 $a_{i,j}$가 주어진다($1\le i\le n$, $1\le j\le m$에 대해 $0\le a_{i,j}\le 100$). 행렬의 각 열은 한 번의 $d$도 회전에 해당하는 측정값이다. $a_{i,j}$는 $j$번째 단계에서 $A_i$가 물로 덮인 비율(%)이다.

행성 표면 중 물로 덮인 비율을 출력하라. 절대 오차가 $10^{-6}$ 이하이면 정답으로 인정한다.