题解

思路

第 $i$ 个三角形为 $x\ge x_i,y\ge y_i,x+y\le h_i$，其中 $h_i=x_i+y_i+r_i$。任意非空子集的交仍是同向三角形，腰长

奇覆盖指示函数满足 $\sum_{\emptyset\ne S}(-2)^{|S|-1}\prod_{i\in S}I_i$。

做法

枚举所有非空子集，求交集腰长，并把 $(-2)^{|S|-1}L^2$ 累加到两倍面积。最终整数除以2，并按奇偶输出 .0 或 .5。小范围可枚举单位方格的两个半格；中档可扫描整数宽竖条，在中点计算一维区间异或长度。

复杂度

时间复杂度 $O(n2^n)$，空间复杂度 $O(n)$。最大中间量小于 $3\times10^{16}$，使用 64 位整数。