三角分区

Question

这是2010年太平洋ACM-ICPC比赛的一个问题.它的要点是试图找到一种方法将三角形内的一组点划分为三个子三角形,这样每个分区恰好包含三分之一的点.

输入:

• 边界三角形的坐标: (v1x,v1y),(v2x,v2y),(v3x,v3y)
• 一个数字,3n < 30000表示三角形内的点数
• 3n点数的坐标:(x_i,y_i)fori=1...3n

输出:

• (sx,sy)将三角形分成3个子三角形的点,使每个子三角形包含精确的n点.

分割点将边界三角形分割为子三角形的方式如下:从分割点到三个顶点中的每一个绘制一条线.这将三角形划分为3个子三角形.

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

这是n=2(6分)问题的一个例子.我们给出了每个彩色点的坐标和大三角形的每个顶点的坐标.分裂点以灰色圈出.

有人建议比这更快的算法O(n^2)吗？

Answer 1

这是一个O(n log n)算法。我们假设没有退化。

\n\n

高级思想是，给定一个三角形PQR，

\n\n

   P\n  C \\\n /  S\\\nR-----Q\n

\n\n

我们最初将中心点放置C在P。C向滑动，R直到n三角形内有点CPQ且S线段上有一个 ()点CQ。C朝某个方向滑动，Q直到任一三角形CRP不再有缺陷（扰动C，我们就完成了）或CP达到一个点。在后一种情况下，滑C离P直到任一三角形CRP不再有缺陷（我们完成了）或CQ到达一个点，在这种情况下我们开始再次C滑向Q。

\n\n

显然，该实现不能 \xe2\x80\x9cslide\xe2\x80\x9d 点，因此对于涉及 的每个三角形C，对于S该三角形除 之外的每个顶点C，将三角形内的点存储在按角度排序的二叉搜索树中S。这些结构足以实现该动力学算法。

\n\n

我在没有证据的情况下断言这个算法是正确的。

\n\n

从运行时间来看，每个事件都是一个点线交点，可以及时处理O(log n)。角度PC和都是单调的QC，RC因此每条O(1)线最多碰到每个点一次。

\n