包含点的三角形数（0,0）

• Z时代
• 2024-01-10
• 分类：问答

首先，要归功于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