题目理解

我们有一个正交多边形蛋糕，需要从原点 $(0,0)$ 发出 $k$ 条射线，将蛋糕分成 $k+1$ 个面积相等的部分。

问题转化

设蛋糕总面积为 $S$，从原点出发、极角为 $\theta$ 的射线将蛋糕分成两部分，其中一部分的面积为 $F(\theta)$。我们需要找到 $k$ 个极角 $\theta_1, \theta_2, \ldots, \theta_k$，使得：

$$F(\theta_i) = \frac{i}{k+1} \times S, \quad i=1,2,\ldots,k $$

面积函数推导

关键观察

对于正交多边形的每条边，从原点出发的射线扫过的面积可以表示为极角 $\theta$ 的函数。由于多边形的边平行于坐标轴，面积函数具有特殊形式。

分段函数表示

面积函数 $F(\theta)$ 可以表示为分段函数，每段的形式为：

$$F(\theta) = a\tan\theta + b\cot\theta + c$$

其中系数 $a, b, c$ 由多边形的几何特性决定。

系数计算原理

• 垂直边 $(x = \text{常数})$：当射线与垂直边相交时，贡献形式为 $a\tan\theta + c$
• 水平边 $(y = \text{常数})$：当射线与水平边相交时，贡献形式为 $b\cot\theta + c$

具体来说：

• 对于从 $(x,y_1)$ 到 $(x,y_2)$ 的垂直边（$y_1 < y_2$）：

  • 在极角区间 $[\alpha,\beta]$ 内（其中 $\alpha = \arctan(y_1/x)$, $\beta = \arctan(y_2/x)$）
  • 面积贡献为：$\frac{1}{2}x^2(\tan\beta - \tan\alpha) - x(y_2 - y_1)$
  • 整理得系数：$a = \frac{1}{2}x^2$, $c = -xy_1$（在 $\alpha$ 处）和 $a = -\frac{1}{2}x^2$, $c = xy_2$（在 $\beta$ 处）

• 对于从 $(x_1,y)$ 到 $(x_2,y)$ 的水平边（$x_1 < x_2$）：

  • 在极角区间 $[\alpha,\beta]$ 内（其中 $\alpha = \arctan(y/x_2)$, $\beta = \arctan(y/x_1)$）
  • 面积贡献为：$\frac{1}{2}y^2(\cot\alpha - \cot\beta) + y(x_2 - x_1)$
  • 整理得系数：$b = -\frac{1}{2}y^2$, $c = yx_1$（在 $\alpha$ 处）和 $b = \frac{1}{2}y^2$, $c = -yx_2$（在 $\beta$ 处）

算法实现

预处理阶段

1. 多边形定向：确保顶点按逆时针顺序排列

   int s = 0;
   for (int i = 0; i < n; i++)
       s += det(v[i], v[(i + 1) % n]);
   if (s < 0)
       s = -s, reverse(v.begin(), v.end());
   

2. 构建分段函数：对于每条边，计算其在端点极角处的函数变化

   map<db, Func> mp;
   for (int i = 0; i < n; i++) {
       int j = (i + 1) % n;
       auto A = polar_angle(v[i]);
       auto B = polar_angle(v[j]);
       
       if (v[i].x == v[j].x) {  // 垂直边
           // 计算系数 a, c 并更新 mp[A] 和 mp[B]
       } else {  // 水平边
           // 计算系数 b, c 并更新 mp[A] 和 mp[B]
       }
   }
   

求解阶段

1. 累积函数：按极角顺序遍历，累积当前区间的面积函数

   Func f;
   for (auto it = mp.begin(); next(it) != mp.end(); it++) {
       auto [u, d] = *it;
       auto v_ang = next(it)->first;
       f = (f + d);  // 累积函数
   

2. 二分查找：在当前区间内寻找满足面积条件的切割点

   while (now < k && now / (db)k * s <= f.calc(v_ang) + eps) {
       db L = u, R = v_ang;
       db tar = now / (db)k * s;  // 目标面积
       
       // 60次二分迭代保证精度
       for (int t = 0; t < 60; t++) {
           db M = (L + R) / 2;
           if (f.calc(M) <= tar + eps)
               L = M;
           else
               R = M;
       }
       ans.push_back(L);
       now++;
   }
   

3. 输出结果：将极角转换为单位圆上的坐标

   for (auto x : ans)
       cout << cosl(x) << " " << sinl(x) << "\n";
   

复杂度分析

• 预处理：$O(n\log n)$（主要来自极角排序）
• 二分查找：$O(k \log \frac{1}{\epsilon})$，其中 $\epsilon = 10^{-15}$ 是精度要求
• 总复杂度：$O(n\log n + k \log \frac{1}{\epsilon})$，对于 $n,k \leq 3\times 10^5$ 可接受

数值稳定性

• 使用 long double 保证计算精度
• 在 $\tan\theta$ 接近 $0$ 时特殊处理，避免除零错误
• 二分查找使用相对误差判断

算法优势

1. 几何直观：利用正交多边形的特性简化面积计算
2. 数值稳定：分段函数表示避免复杂的几何求交
3. 高效准确：二分查找保证在给定精度内找到解

代码总结

代码的核心是：

1. 将多边形分解为垂直边和水平边
2. 为每条边计算其对面积函数的贡献
3. 按极角排序后累积函数值
4. 在每個区间内二分查找满足面积条件的切割点
5. 输出对应的单位向量坐标

这种方法巧妙地利用了正交多边形的几何特性，将复杂的面积计算转化为分段函数的求值问题，是计算几何中的一个优美解法。