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

Question

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

algorithmdata-structures

3

首先，感谢Topcoder，因为这个问题曾在他们的SRMs中使用过（但他们没有对此进行编辑...）

在这个问题中，我会得到n个点（其中n在1到1000之间）。对于每三个点，显然有一个连接它们的三角形。问题是，有多少个三角形包含点（0,0）。

我尝试看看这个线程： triangle points around a point 但我无法理解使用了哪些数据结构/如何使用它们来解决这个问题。

这个问题的一个明显的朴素解决方案是使用低效的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;
    }
}

- user3904840

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- advocateofnone · Accepted Answer

假设有一个三角形，其三个点为p1=(x_1, y_1)、p2=(x_2, y_2)和p3=(x_3, y_3)。p1、p2和p3是位置向量。如果原点在三角形内部，则任意一个位置向量与其他两个的叉积符号不同（一个负数，一个正数）。但如果原点在外部，则会有一个点与其他两个点的叉积均为负数。因此，对于每个点i，找到其叉积小于0的点。现在，如果您选择这些点中的任意两个并与点i一起构成一个三角形，则原点将在此三角形外部。因此，从res中减去这些点的选择（从这些点中选择2个+点i）。这是迄今为止许多人实现的最佳解决方案，因为它没有使用double等时存在精度问题。