BZOJ2178/圆的面积并

Posted on By 二价氢

#题目描述

给出N个圆,求其面积并

#做法

  1. 去掉被包含的圆
  2. 求一个圆被其它圆覆盖的补集
  3. 排序,找没被覆盖的弧

突然发现圆的面积并和圆的周长并好像的样子

#复杂度分析 \(O(N^2 + N^2 \log N)\)其中,\(O(N^2)\)为枚举,\(O(N^2 \log N)\)为枚举后的整理,每次\(O(N\log N)\),进行\(O(N)\)次

#AC Code

使用std::multiset作为平衡树