통계학자들

시간 제한1초메모리 제한128 MB

요약

칸마다 인구 수가 주어진 격자에서 넓이가 [a,b]에 드는 모든 축 정렬 부분 직사각형의 평균 밀도 중앙값을 구한다.

난이도: 어려움10점 중 8점
유형: 누적 합, 이분 탐색, 정렬
정답자: 아직 제출이 없습니다

문제

통계학자들은 다양한 통계량을 계산하기를 좋아한다. 가장 간단한 척도 중 하나는 평균으로, 모든 값의 합을 값의 개수로 나눈 값이다. 또 다른 척도는 중앙값으로, 모든 값을 정렬했을 때 가운데에 오는 값이다. 값의 개수가 짝수이면 가운데 두 값의 평균을 중앙값으로 한다.

이러한 척도는 예를 들어 한 나라의 인구나 그 일부를 설명하는 데 쓸 수 있다. Anne Jensen, Maria Virtanen, Jan Hansen, Erik Johansson, Jón Þórsson은 북유럽 국가에 통계학자가 얼마나 있는지를 통계적으로 측정하고자 한다. 더 정확히는 단위 넓이당 통계학자 수를 알고 싶어 한다. 인구가 넓게 퍼져 있으므로, 이들은 MAD(Median of All Densities, 모든 밀도의 중앙값)라는 새로운 측정값을 사용한다.

지도 위에 정사각형 격자를 덮는다.
넓이가 허용 범위 안에 있는 모든 격자 정렬 직사각형에 대해 밀도, 즉 단위 넓이당 통계학자의 평균 수(직사각형 안의 합을 그 넓이로 나눈 값)를 계산한다.
가능한 모든 직사각형에 대해 이를 반복한 뒤, 모든 밀도의 중앙값을 MAD로 한다.

격자와 허용되는 직사각형 넓이 범위가 주어질 때 MAD를 구하라.

입력

첫째 줄에는 격자의 높이 $h$ 와 너비 $w$ 가 공백으로 구분되어 주어진다 ( $1 \le h \le 140$ , $1 \le w \le 120$ ).

둘째 줄에는 허용되는 직사각형 넓이의 하한 $a$ 와 상한 $b$ 가 공백으로 구분되어 주어진다. 즉 고려하는 모든 직사각형의 넓이는 $[a, b]$ 안에 있으며 $1 \le a \le b \le w \times h$ 이다.

이어서 $h$ 개의 줄에 각각 $w$ 개의 정수 $s$ 가 공백으로 구분되어 주어지며, 이는 각 칸에 있는 통계학자의 수이다 ( $0 \le s \le 10000$ ).

넓이가 $[a, b]$ 안에 있는 직사각형은 항상 적어도 하나 존재한다.

출력

MAD, 즉 단위 넓이당 통계학자 수를 소수점 아래 셋째 자리까지 반올림하여 한 줄에 출력한다.

예제2

예제 1
입력
```
4 2
1 8
6 5
2 5
2 9
7 13
```
예상 출력
```
5.250
```
예제 2
입력
```
2 3
2 4
6 1 4
2 7 1
```
예상 출력
```
3.667
```