三角分区 [英] Triangle partitioning

问题描述

这是在2010年的太平洋ACM-ICPC竞赛的一个问题。它的要点是试图找到一种方法，使每个分区包含点恰好第三分区一组三角形内点为三个子三角形。

This was a problem in the 2010 Pacific ACM-ICPC contest. The gist of it is trying to find a way to partition a set of points inside a triangle into three subtriangles such that each partition contains exactly a third of the points.

输入：

• 在边界三角形的坐标：（V1X，V1Y），（V2X，V2Y），（V3X，v3y）
• 若干 3N＆LT; 30000 重presenting点，位在三角形内的数
• 的 3N 点坐标：（x_i，y_i）为 I = 1 ... 3N

• Coordinates of a bounding triangle: (v1x,v1y),(v2x,v2y),(v3x,v3y)
• A number 3n < 30000 representing the number of points lying inside the triangle
• Coordinates of the 3n points: (x_i,y_i) for i=1...3n

输出：

• 在一个点（SX，SY），简单地将三角形分为3子三角形，使得每个subtriangle正好包含 N 点。

• A point (sx,sy) that splits the triangle into 3 subtriangles such that each subtriangle contains exactly n points.

分割点分割的边界三角形成子三角形的方法是如下：绘制从分裂点的线来分别在三个顶点。这将划分成三角形3子三角形。

The way the splitting point splits the bounding triangle into subtriangles is as follows: Draw a line from the splitting point to each of the three vertices. This will divide the triangle into 3 subtriangles.

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

We are guaranteed that such a point exists. Any such point will suffice (the answer is not necessarily unique).

这是问题的为例N = 2 （6分）。我们给出每个的着色点和大三角形的每个顶点的坐标的坐标。在分割点盘旋灰色。

Here is an example of the problem for n=2 (6 points). We are given the coordinates of each of the colored points and the coordinates of each vertex of the large triangle. The splitting point is circled in gray.

有人建议算法的速度比为O（n ^ 2）？

Can someone suggest an algorithm faster than O(n^2)?

推荐答案

下面是一个为O（n log n）的算法。假设没有退化。

Here's an O(n log n) algorithm. Let's assume no degeneracy.

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

The high-level idea is, given a triangle PQR,

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

我们首先把中心点 C 在 P 。幻灯 C 走向研究，直到有 N 里面的点三角 CPQ 和一个（取值）的片段 CQ 。幻灯 C 走向问：，直到三角形 CRP 不再缺陷（扰动 C 键，就完成了）或 CP 打一个点。在后一种情况下，幻灯片 C 远离 P ，直到三角形 CRP 已不再是缺陷（我们正在做的）或 CQ 打一个点，在这种情况下，我们开始滑动 C 走向问：了。

we initially place the center point C at P. Slide C toward R until there are n points inside the triangle CPQ and one (S) on the segment CQ. Slide C toward Q until either triangle CRP is no longer deficient (perturb C and we're done) or CP hits a point. In the latter case, slide C away from P until either triangle CRP is no longer deficient (we're done) or CQ hits a point, in which case we begin sliding C toward Q again.

显然，执行不能滑点，所以对于涉及每个三角形 C ，为每个顶点取值的那个三角形比 C 等，存储在三角形内的点在二叉搜索树排序角度取值。这些结构足以实现这一运动的算法。

Clearly the implementation cannot "slide" points, so for each triangle involving C, for each vertex S of that triangle other than C, store the points inside the triangle in a binary search tree sorted by angle with S. These structures suffice to implement this kinetic algorithm.

我断言没有证据表明该算法是正确的。

I assert without proof that this algorithm is correct.

对于运行时间，每个事件是一个点线相交，并能及时处理 O（log n）的。该角度 PC 和 QC 和 RC 都是单调的，所以每个 O（1）线在击中了每个点最多一次。

As for the running time, each event is a point-line intersection and can be handled in time O(log n). The angles PC and QC and RC are all monotonic, so each of O(1) lines hits each point at most once.

这篇关于三角分区的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！