包含点的三角形数(0,0)

首先,要归功于Topcoder,因为此问题已在其SRM之一中使用(但没有对此进行编辑。)

在这个问题上,我得到n分(其中n在1到1000之间)。对于每三个点,显然有一个三角形将它们连接起来。问题是,这些三角形中有多少个包含点(0,0)。

但是我无法理解使用了什么数据结构/如何使用它们来解决此问题。

一个明显的天真的解决方案是使用效率低的O(n ^ 3)算法并搜索所有点。但是,有人可以帮助我提高效率,并在O(n ^ 2)时间内做到这一点吗?

以下是Petr对这个问题的解决方案…它很短,但是有一个我无法理解的大主意。

/**

* Built using CHelper plug-in

* Actual solution is at the top

*/

public class TrianglesContainOrigin {

public long count(int[] x, int[] y) {

int n = x.length;

long res = (long) n * (n - 1) * (n - 2) / 6;

for (int i = 0; i < n; ++i) {

int x0 = x[i];

int y0 = y[i];

long cnt = 0;

for (int j = 0; j < n; ++j) {

int x1 = x[j];

int y1 = y[j];

if (x0 * y1 - y0 * x1 < 0) {

++cnt;

}

}

res -= cnt * (cnt - 1) / 2;

}

return res;

}

}

回答:

假设有一个3点的三角形 , 和

。设p1,p2,p3为位置向量。如果原点位于其中,则任何一个位置向量与其他两个的叉积的符号将不同(一个为负,一个为正)。但是,如果原点在外面,则将有一个点与其他两个点的叉积为负。因此,对于每个点,我会找到叉积小于0的点。现在,如果您选择这些点中的任意两个并与点i一起组成一个三角形,则原点将位于该三角形之外。从这些点+点i)。到目前为止,这是许多实施的最佳解决方案,因为它不存在双精度等问题。

在此处输入图片说明

以上是 包含点的三角形数(0,0) 的全部内容, 来源链接: utcz.com/qa/414512.html

回到顶部