Flooded!

To enable homebuyers to estimate the cost of flood insurance, a real-estate firmprovides clients with the elevation ofeach 10-meter by 10-meter square of land in regions where homes may be purchased.Water from rain, melting snow,and burst water mains will collect first in those squares with the lowest elevations,since water from squares of higherelevation will run downhill. For simplicity, we also assume that storm sewers enablewater from high-elevation squaresin valleys (completely enclosed by still higher elevation squares) to drain to lowerelevation squares, and that water willnot be absorbed by the land.

 

From weather data archives, we know the typical volume of water that collects in aregion. As prospective homebuyers,we wish to know the elevation of the water after it has collected in low-lyingsquares, and also the percentage of theregion's area that is completely submerged (that is, the percentage of 10-metersquares whose elevation is strictly lessthan the water level). You are to write the program that provides these results.

 

Input 

The input consists of a sequence of region descriptions. Each begins with a pairof integers, m and n, each less than 30,giving the dimensions of the rectangular region in 10-meter units. Immediatelyfollowing are m lines of n integers givingthe elevations of the squares in row-major order. Elevations are given in meters,with positive and negative numbersrepresenting elevations above and below sea level, respectively. The final valuein each region description is an integerthat indicates the number of cubic meters of water that will collect in the region.A pair of zeroes follows the descriptionof the last region.

 

Output 

For each region, display the region number (1, 2, ...), the water level (in metersabove or below sea level) and thepercentage of the region's area under water, each on a separate line. The water leveland percentage of the region's areaunder water are to be displayed accurate to two fractional digits. Follow the outputfor each region with a blank line.

 

Sample Input 

3 325 37 4551 12 3494 83 27100000 0

 

Sample Output 

Region 1Water level is 46.67 meters.66.67 percent of the region is under water.

 

 

 

---

Miguel Revilla2002-06-25


題目描述：
高度較低的地方會先淹水, 問水的高度位置為和?

題目解法：
一種是二分搜索高度, 在此不多說。
但事實上我們可以先排序一下每個地方的高度, 然後查看水淹的高度。
V = (h-a[0])*100+(h-a[1])*100+ (h-a[2])*100 + (h-a[3])*100...
藉此算出高度 h

#include <bits/stdc++.h>
using namespace std;

int main() {
    double V;
    int cases = 0;
    int n, m, A[1005];
    while (scanf("%d %d", &n ,&m) == 2 && n) {
        int x;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                scanf("%d", &A[i*m+j]);
        scanf("%lf", &V);
        n = n*m;
        sort(A, A+n);
        double sum = 0, h = 0;
        A[n] = 1e+10;
        printf("Region %d\n", ++cases);
        for (int i = 0; i < n; i++) {
            sum += A[i];
            h = (V+sum*100)/(i+1)/100.0;
#define eps 1e-6
            if (h < A[i+1]+eps) {
                printf("Water level is %.2lf meters.\n", h);
                printf("%.2lf percent of the region is under water.\n\n", (i+1)*100.0/n);
                break;
            }
        }
    }
    return 0;
}
/*
1 1
37
24
0 0
*/