POJ 3347 Kadj Squares （计算几何）

题意：依次按如图所示放置正方形，即尽可能往左靠，求放完所有正方形后，从高处向下照射竖直平行光，有部分会被照亮的正方形序号。

题解：计算几何
①找出每个正方形的x坐标$b[]$b[]
对于正方形$i$i，b[i] = max(b[i], b[j] + 2 * min(a[i], a[j]) / sqrt(2.0))，$j$j为之前放置的正方形。

②找出每个正方形被覆盖的区域，左边$l$l，右边$r$r
对于正方形$i$i，l = max(l, b[j] + a[j] / sqrt(2.0) - (b[i] - a[i] / sqrt(2.0)))，$j$j为之前放置的正方形，当然在$i$i的边长小于$j$j的边长时才执行，这样$i$i才能被覆盖。
对于正方形$i$i，r = max(r, b[i] + a[i] / sqrt(2.0) - (b[j] - a[j] / sqrt(2.0)))，$j$j为之后放置的正方形，当然在$i$i的边长小于$j$j的边长时才执行，这样$i$i才能被覆盖。
若l + r < 2 * a[i] / sqrt(2.0)，则表示没有被完全覆盖，输出。

当然这样写还是会因为精度问题wa，我们发现数组$a[]$a[]都被除以了根号2，我们将根号2移除，并不影响计算。

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<fstream>
#include<set>
#include<map>
#include<sstream>
#include<iomanip>
#define ll long long
using namespace std;
int n;
double a[55], b[55];
int main() {
	while (~scanf("%d", &n) && n) {
		for (int i = 1; i <= n; i++) {
			scanf("%lf", &a[i]);
		}
		b[1] = a[1];
		for (int i = 2; i <= n; i++) {
			b[i] = 0;
			for (int j = 1; j < i; j++) {
				b[i] = max(b[i], b[j] + 2 * min(a[i], a[j]));
			}
		}
		for (int i = 1; i <= n; i++) {
			double l = 0, r = 0;
			for (int j = 1; j < i; j++) {
				if (a[i] >= a[j]) continue;
				l = max(l, b[j] + a[j] - (b[i] - a[i]));
			}
			for (int j = i + 1; j <= n; j++) {
				if (a[i] >= a[j]) continue;
				r = max(r, b[i] + a[i] - (b[j] - a[j]));
			}
			if (l + r < 2 * a[i]) printf("%d ", i);
		}
		printf("\n");
	}
	return 0;
}