aoj1313（*simpson公式求三维体积）

/* translation: 三维坐标系上有2个棱柱，分别平行与Z轴以及Y轴，现在分别给出它们在XY平面和XZ平面上的底面顶点，求两个棱柱相交部分的体积。 solution: 主要思路是不难，但前提得知道simpson公式。利用该公式即可将积分公式化为普通的公式。然后微积分求出来的既是体积。 */ #include <iostream> #include <cstdio> #include <vector> #include <algorithm> using namespace std; const int maxn = 200 + 5; const double INF = 0x3f3f3f3f * 1.0; int X1[maxn], Y1[maxn], m, n; int X2[maxn], Z2[maxn]; vector<int> xv; double getWidth(int* X, int* Y, int n, double x) { double lb = INF, ub = -INF; for(int i = 0; i < n; i++) { double ax = X[i], ay = Y[i]; double bx = X[(i+1)%n], by = Y[(i+1)%n]; if((ax - x) * (bx - x) <= 0 && ax != bx) { double y = (by - ay) / (bx - ax) * (x - ax) + ay; lb = min(lb, y); ub = max(ub, y); } } return max(0.0, ub-lb); } int main() { //freopen("in.txt", "r", stdin); while(~scanf("%d%d", &m, &n)) { if(m + n == 0) break; for(int i = 0; i < m; i++) scanf("%d%d", &X1[i], &Y1[i]); for(int i = 0; i < n; i++) scanf("%d%d", &X2[i], &Z2[i]); xv.clear(); for(int i = 0; i < m; i++) xv.push_back(X1[i]); for(int i = 0; i < n; i++) xv.push_back(X2[i]); int min1 = *min_element(X1, X1 + m), max1 = *max_element(X1, X1 + m); int min2 = *min_element(X2, X2 + n), max2 = *max_element(X2, X2 + n); sort(xv.begin(), xv.end()); double ans = 0; for(int i = 0; i < xv.size()-1; i++) { double a = xv[i], b = xv[i+1], c = (a + b) / 2; if(c >= min1 && c <= max1 && c >= min2 && c <= max2) { double fa = getWidth(X1, Y1, m, a) * getWidth(X2, Z2, n, a); double fb = getWidth(X1, Y1, m, b) * getWidth(X2, Z2, n, b); double fc = getWidth(X1, Y1, m, c) * getWidth(X2, Z2, n, c); ans += (b - a) / 6 * (fa + 4 * fc + fb); } } printf("%.10f\n", ans); } return 0; }