三角形划分

Question

这是2010年太平洋ACM-ICPC竞赛的一个问题。它的要点是设法将三角形内的一组点划分为三个子三角形，以便每个分区都包含三分之一的点。

输入：

包围三角形的(v1x,v1y),(v2x,v2y),(v3x,v3y)

• A

• 坐标：i=1...3n

的 number 3n < 30000，表示位于3n points：(x_i,y_i)中的点数

输出：

• 把三角形分成3个子三角形的点(sx,sy)，使得每个子三角形都包含精确的n点。

分裂点将包围三角形分割成子三角形的方法如下:从分裂点到三个顶点中的每一个都画一条线。这将把三角形分成三个亚三角形。

我们得到保证这一点是存在的。任何这样的观点都足够了(答案不一定是唯一的)。

下面是n=2问题的一个例子(6分)。给出了每个着色点的坐标和大三角形每个顶点的坐标。分裂点用灰色圈起来。

​

​

有人能提出比O(n^2)更快的算法吗？

Answer 1

这是一个O(n log n)算法。让我们假设没有简并。

高层的想法是，给出一个三角形PQR，

   P
  C \
 /  S\
R-----Q

我们最初将中心点C放在P上。将C滑向R，直到三角形CPQ中有n点，而分段CQ上有一个(S)点。将C滑向Q，直到三角形CRP不再有缺陷(扰动C，我们就完成了)，或者CP达到了一个点。在后一种情况下，将C从P中移开，直到三角形CRP不再有缺陷(我们已经完成)或CQ到达某个点为止，在这种情况下，我们再次开始向Q滑动C。

显然，实现不能“滑动”点，因此对于涉及C的每个三角形，对于除C以外的三角形的每个顶点S，将三角形内的点存储在按S角排序的二叉树中。这些结构足以实现这一动力学算法。

我断言没有证据证明这个算法是正确的。

至于运行时间，每个事件都是一个点线交集，可以在时间O(log n)中处理。角度PC、QC和RC都是单调的，因此每条O(1)线最多只打一次。

Answer 2

主要思想是:如果我们有这条线，我们可以试着用线性搜索在它上找到一个点。如果行不够好，我们可以使用二进制搜索来移动它。

​

​

1. 根据顶点A的方向对点进行排序。对B和C也进行排序。
2. 将顶点A的当前范围设置为顶点A范围内的所有
3. 2中间点。这两点定义了“A”的子范围。获取位于这些points.
4. Iterate之间的、位于B和AD之间的所有点的行AD (从BA开始)。当发现n点时停止。选择从B到n的方向子范围，以及在n之后的下一个方向(如果n之后没有点，请使用BC)。如果可以找到小于n点的值，则将顶点A的当前范围设置为当前范围的左半，然后转到步骤3。n
5. 与步骤4相同，但对于顶点A子程A、B、C相交，则从那里选择任意点并完成。否则，如果A&B更接近A，则将顶点A的当前范围设置为当前范围的右半部分，然后转到步骤3。否则，将顶点A的当前范围设置为当前范围的左半，然后转到步骤3。

复杂性:排序O(n * log n)，搜索O(n * log n)。(二元搜索和线性搜索的结合)。

Answer 3

这里有一种方法，采用O(log )传递的成本n个。

每一次传递都从一个初始点开始，该点将三角形划分为亚三角形。如果每个人都有n点，我们就完成了。如果不是，考虑离期望的n最远的子三角形，假设它有太多，只是暂时的。失衡之和为零，因此其他两个亚三角形中至少有一个点太少。第三个子三角形要么也太少，要么正好有n个点--否则原始的子三角形就不会有最大的偏差。

取最不平衡的亚三角形，并考虑沿这条线移动中心点，使之远离它。当你这样做的时候，最不平衡点的不平衡将会减少。对于三角形中的每个点，当你移动中心点时，你可以计算出该点在最不平衡的子三角形中或从最不平衡的子三角形中交叉的时间。因此，你可以在时间n中计算出移动中心点的位置，给出最不平衡的三角形，任何想要的计数。

当你移动中心点时，你可以选择点是否在我们最不平衡的子三角形中移动，但你不能选择其他两个子三角形中的哪一个，或者从哪两个子三角形中移动--但是你可以很容易地预测哪一边是你要滑动的中心点，这样你就可以沿着这条线移动中心点，得到移动后的最大偏差。在最坏的情况下，所有移动的点都进入或离开了完全平衡的子三角形。然而，如果不平衡的子三角形有n+k点，通过移动其中的k/2，在最坏的情况下，你可以移动到它和先前平衡的子三角形是k/2的情况。第三个子三角形在另一个方向上可能仍然是不平衡的，直到k，但在这种情况下，第二次遍历会将最大不平衡降低到k/2以下。

因此，在一个大不平衡的情况下，我们可以在最坏的情况下将它减少一个常数因子在上述算法的两次通过，所以在O(log )通过，不平衡将足够小，我们进入特殊的情况下，我们担心的过剩最多一点。在这里，我将猜测这样的特殊情况的数目实际上是可在一个程序中列举的，并且费用相当于一个小的固定的加法。