CVBB ACM Team

$n$个只有相离和包含关系的圆，覆盖奇数次的区域为阴影，偶数次为空白，选择一些圆将原图分为两部分，每部分分别计算面积，使阴影部分面积最大

• 第一种做法是贪心，即把覆盖两次的圆取出来，剩下的圆不动。
  • 关于证明，首先通过画图不难看出来，假设第二部分初始是空白的，那么将某个圆移动至第二部分，如果该圆覆盖区域变为阴影，那么总面积一定是增加或不变的，反之会减少或不变。
  • 同理，可以把圆转换为任意形状的闭合区域。
  • 当把覆盖两次的圆移动至左侧后，对于两次以上的圆，无论怎么移动，第二部分出现空白，总面积$\leq$最优面积
  • 如果移动覆盖一次的圆，实际上就是相当于把覆盖两次及以上的圆移动到第二部分，肯定是不优的。