1782.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 1782 on 2006-10-01 at 10:12:07 */
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 51200;

class Cistern {
public:
	int b, h, s;
	void make() { int d, w; scanf("%d %d %d %d", &b, &h, &d, &w); s = d*w; }
	int totalH() const { return b+h; }
	int totalV() const { return h*s; }
	double water(double) const;
};
double Cistern::water(double ch) const {
	if(ch < b) return 0;
	else if(ch > b+h) return h*s;
	else return (ch-b)*s;
}

int main()
{
	int T;
	Cistern c[N];
	
	scanf("%d", &T);
	for(int t = 0; t < T; t++) {
		int n; scanf("%d", &n);
		for(int i = 0; i < n; i++) c[i].make();
		int v, tv = 0; scanf("%d", &v);
		for(int i = 0; i < n; i++) tv += c[i].totalV();
		if(tv < v) { printf("OVERFLOW\n"); continue; }
		double l = 1e20, h = 0;
		for(int i = 0; i < n; i++) { l <?= c[i].b; h >?= c[i].totalH(); }
		while(h-l > 1e-3) {
			double mid = (h+l)/2, cv = 0;
			for(int i = 0; i < n; i++) cv += c[i].water(mid);
			if(cv >= v) h = mid;
			else l = mid;
		}
		printf("%.2lf\n", h);
	}
	
	return 0;
}