三角形分区

这是2010年太平洋ACM-ICPC竞赛中的一个问题。它的要点是试图找到一种方法来将一个三角形内的一组点分成三个子三角形，这样每个分区只包含三分之一的点。三角形分区

输入：边界三角形的

坐标：(v1x,v1y),(v2x,v2y),(v3x,v3y)
若干3n < 30000表示躺在三角形
的3n点的坐标内部的点的数目：(x_i,y_i)为i=1...3n

输出：

，其将三角形分成3子三角形，使得每个子三角形精确地包含n点A点(sx,sy)。

分裂点将边界三角形划分为子三角形的方式如下：从分裂点到三个顶点中的每一个绘制一条线。这将把三角形分成3个子三角形。

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

以下是n=2（6分）的问题示例。我们给出了每个彩色点的坐标和大三角形每个顶点的坐标。分裂点以灰色圈起来。

enter image description here

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

来源

2011-11-01 tskuzzy

你应该问这里：http://math.stackexchange.com/ – Ariel

这是一个算法问题，而不是一个数学问题。 – tskuzzy

我会用一个简单的方法。 – wildplasser

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

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

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

我们最初放置中心点C在P。向R滑动C，直到在CQ段上存在三角形CPQ内的n个点和一个（S）。向Q滑动C，直到三角形CRP不再有缺陷（扰动C，我们完成）或CP达到一个点。在后一种情况下，从P滑动C，直到三角形CRP不再有缺陷（我们完成）或CQ达到一个点，在这种情况下我们开始再次向Q滑动C。

显然执行不能“滑动”点，所以对于每个三角形涉及C，为每个顶点比其它C那个三角形的S，三角形内部的点存储在由角度S排序二进制搜索树。这些结构足以实现这个动力学算法。

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

至于运行时间，每个事件是一个点线路口，可以在时间O(log n)处理。角度PC和QC和RC都是单调的，所以每个O(1)线最多一次点击每个点。

来源

2011-11-01 16:13:28 rom

我预见到当CP击中多个点而不是只有一个时，会出现邪恶的角落案例。 – hugomg

@missingno这是我假定的退化，就像计算几何中的标准一样。一般情况下，如果有三个共线点，则无法解决问题。 – rom

这就是我所设想的degenaracy，因为在编程竞赛中是标准的:)但是我现在完全相信，因为共线情况并没有什么意义。 – hugomg

这是一种每次都花费O（log n）次传递成本n的方法。

每一遍都从一个初始点开始，它将三角形分成三角形。如果每个都有n个点，我们就完成了。如果不是，则考虑离所期望的n最远的子三角形。假设它有太多，就目前而言。不平衡总和为零，因此其他两个子三角中至少有一个点数太少。第三个小三角要么太少，要么正好有n个 - 或者原始小三角不会有最大的差异。

采取最不平衡的三角形，并考虑沿着离开它的线移动中心点。当你这样做时，最不平衡点的不平衡将会减少。对于三角形中的每个点，当移动中心点时，可以计算出该点何时进入或离开最不平衡的子三角形。因此，您可以及时制定出移动中心点的位置，以便给出最不平衡的三角形任何所需的计数。

当你移动中心点时，你可以选择点是否移动到最不平衡的子三角之外，但是你不能选择其他两个子三角中的哪一个或者哪一个 - 但是你可以很容易地预测哪个子三角从你滑动中心点的线的哪一侧开始，所以你可以沿着这条线移动中心点，以获得移动后最大的最小偏差。在最坏的情况下，所有移动的点都会进入或退出完全平衡的子三角。然而，如果不平衡的小三角具有n + k个点，通过移动k/2个点，最坏的情况下，它可以移动到它和先前平衡的小三角出现k/2的情况。第三小三角可能仍然不平衡达到k，在另一个方向，但在这种情况下，第二次通过将最大不平衡减少到k/2以下。

因此，在大的不平衡情况下，我们可以在上述算法的两遍中最大限度地减少一个常数因子，所以在O（log n）过程中，不平衡将会小到足以使我们变得特别我们担心至多有一点过量的情况。在这里，我猜测这种特殊情况的数量在一个程序中实际上是可以计算的，而且这个成本相当于一个小的不断增加。

来源

2011-11-01 18:40:38 mcdowella

主要思想是：如果我们有了线，我们可以尝试使用线性搜索来找到它的一个点。如果线路不够好，我们可以使用二分查找来移动它。

enter image description here

排序点基于从顶点A方向。将它们排序为B和C。
设置顶点A的当前范围为所有点。
从顶点A的范围中选择2个中点。这两点为'A'定义了子范围。获取一些线AD躺在这些点之间。
迭代所有位于B和AD之间的点（从BA开始）。当发现n点时停止。选择从B到n和n（如果在n之后没有点，请使用BC）之后的下一个方向的子范围。如果找不到n点，则将顶点A的当前范围设置为当前范围的左半部分，然后转到步骤3.
与第4步相同，但是对于顶点C。
如果子范围A，B,C相交，从那里选择任何点并完成。否则，如果A&B更接近A，则将顶点A的当前范围设置为当前范围的右半部分，并转到步骤3.否则，将顶点A的当前范围设置为当前范围的左半部分并转到步骤3.