用容斥原理计算被Hyperplane切割后的Hyperrectangle体积 » RNG

RNG
RNG.cpp


#include <cmath>
#include <cstdio>

long double gao(int n, long double x[], long double y) {
	long double add = 0, sub = 0;
	for (int i = 0; i < (1 << n); ++i) {
		long double z = 0;
		for (int j = 0; j < n; ++j) {
			if (i & (1 << j)) {
				z += x[j];
			}
		}
		if (y > z) {
			if (__builtin_parity(i)) {
				sub += powl(y - z, n);	// pow => WA
//				printf("- %lf: %lf\n", y - z, ret);
			} else {
				add += powl(y - z, n);
//				printf("+ %lf: %lf\n", y - z, ret);
			}
		}
	}
	return add - sub;
}

int main() {
	int re, n;
	long double a, b, p, y, x[16];

	scanf("%d", &re);
	for (int ri = 1; ri <= re; ++ri) {
		scanf("%d%Lf%Lf", &n, &a, &b);
		p = 1;
		y = 0;
		for (int i = 0; i < n; ++i) {
			scanf("%Lf", &x[i]);
			p /= x[i] * (i + 1);
			y += x[i];
		}
		a = (a + y) / 2;
		b = (b + y) / 2;
	//	printf("%lf %lf\n", gao(n, x, b), gao(n, x, a));
		p *= gao(n, x, b) - gao(n, x, a);
		printf("%.9Lf\n", fabsl(p));
	}

	return 0;
}

//ID 	DATE 	USER	PROBLEM	RESULT 	TIME 	MEM 	LANG
//3896547 	2010-08-07 09:47:53 	watashi	Random Number Generator	accepted 	0.02 	2.6M 	C++ 4.3.2
Leave a Reply