题意是放若干个正方体，问说最多能放多少个，使得平衡。
考虑如果只有两个正方体，则上面的正方体的重心要在下面正方体的顶面的范围之内，因为这样，可以把上面的正方体等价为一个质量一样大的，位置在重心的点。如果有多个物体，则从最上面开始判断，平衡之后，就把前n个物体求下重心，看成一个点，看是否能放在第n+1个物体上。
代码 #include < iostream > #include < string > #include < stdio.h > #include < stdlib.h > #include < algorithm > #include < string .h > #include < vector > #include < math.h > #include < map > #include < time.h > #include < queue > #include < set > using namespace std; const int MAX = 105 ; struct NODE{ int x1, y1, x2, y2; double cx, cy; NODE() {} NODE( int _x1, int _y1, int _x2, int _y2) { x1 = min(_x1, _x2); y1 = min(_y1, _y2); x2 = max(_x1, _x2); y2 = max(_y1, _y2); cx = (x1 + x2) * 1.0 / 2 ; cy = (y1 + y2) * 1.0 / 2 ; } double vol() { double a = x2 - x1; return a * a * a; }}node[MAX]; int n;pair < double , double > center[MAX][MAX]; int main(){ while (scanf( " %d " , & n) != EOF) { for ( int i = 1 ; i <= n; i ++ ) { int a, b, c, d; scanf( " %d%d%d%d " , & a, & b, & c, & d); node[n + 1 - i] = NODE(a, b, c, d); } int ans = 0 ; for ( int i = 1 ; i <= n; i ++ ) { double M = 0 ; double x = 0 , y = 0 ; for ( int j = i; j <= n; j ++ ) { M += node[j].vol(); x += node[j].vol() * node[j].cx; y += node[j].vol() * node[j].cy; center[i][j].first = x / M; center[i][j].second = y / M; } } for ( int i = n; i >= 1 ; i -- ) { int j; for (j = i; j <= n - 1 ; j ++ ) { if (center[i][j].first < node[j + 1 ].x1) break ; if (center[i][j].first > node[j + 1 ].x2) break ; if (center[i][j].second < node[j + 1 ].y1) break ; if (center[i][j].second > node[j + 1 ].y2) break ; } if (j <= n - 1 ) break ; ans ++ ; } printf( " %d\n " , ans); }} /* 20 0 3 31 0 4 320 0 3 32 0 5 330 0 3 3 1 0 4 32 0 5 3 */
转载于:https://www.cnblogs.com/litstrong/archive/2010/11/02/1866858.html
