一看范围那么小，就知道是状压暴力容斥。题目可以转化为，求 (t) 个三角形的交的面积，乘一个系数 (k_t) 作为贡献。
首先第一步，求交的面积。由于三角形都是相同方向的，直角边平行坐标轴的等腰直角三角形，我们有除了计算几何以外更方便的方法。
考虑到如果有交，那么交一定也是一个三角形。这个三角形的左下角顶点坐标很好求，是 ((max(x_i),max(y_i)))。那么就差求边长或者斜边了。显然，斜边一定是最靠“左下”的那根直线，即 (x + y) 最小的那根直线，这个其实就是直线 (x+y=min(x_i+y_i+r_i))。这样，左下角顶点和斜边方程找到以后，面积也就好求很多了。(S=dfrac{(min(x_i+y_i+r_i)-max(x_i)-max(y_i))^2}{2})。另外，如果没有交，需要特判一下。
然后第二步，求容斥系数。我们需要系数 (k_i)，满足 (t) 个三角形的交被算了恰好 ([2 mid t]) 次。即
[sum_{i=0}^t{t choose i}k_i=[2
mid t]
]
看起来好像二项式反演的式子。我们设 (g_t=[2 mid t])，那么：
[g_t=sum_{i=0}^t {t choose i}k_i
]
[k_t=sum_{i=0}^t {t choose i} (-1)^{t-i}g_i
]
(i) 为偶数的时候没有贡献，那么:
[k_t=(-1)^{t-1}sum_{i=0}^t {t choose i}[2
mid i]
]
二项式定理：
[k_t=(-1)^{t-1}frac{(1+1)^t-(1-1)^t}{2}=(-2)^{t-1}
]
最后直接暴力(2^n)容斥即可。
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <ctime>
#include <algorithm>
typedef long long ll;
template <typename T> inline void read(T &x) {
x = 0; char c = getchar(); bool flag = false;
while (!isdigit(c)) { if (c == '-') flag = true; c = getchar(); }
while (isdigit(c)) { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); }
if (flag) x = -x;
}
using namespace std;
const int inf = 987654321;
inline void MIN(int &a, int b) {
if (b < a) a = b;
}
inline void MAX(int &a, int b) {
if (b > a) a = b;
}
int n;
int X[12], Y[12], R[12];
int mi[12];
ll ans;
inline ll Pow(int x) {
return 1ll * x * x;
}
inline void work(int s) {
int mn = inf, mxx = -inf, mxy = -inf, ct = 0;
for (register int i = 0; i < n; ++i) if ((s >> i) & 1) {
MIN(mn, X[i] + Y[i] + R[i]);
MAX(mxx, X[i]);
MAX(mxy, Y[i]);
++ct;
}
ans += 1ll * mi[ct - 1] * Pow(max(0, mn - mxx - mxy));
}
int main() {
read(n);
for (register int i = 0; i < n; ++i) read(X[i]), read(Y[i]), read(R[i]);
mi[0] = 1;
for (register int i = 1; i <= n; ++i) mi[i] = -2 * mi[i - 1];
int All = (1 << n) - 1;
for (register int s = 1; s <= All; ++s) {
work(s);
}
printf("%.1lf
", 0.5 * ans);
return 0;
}