包含点的三角形数（0,0） [英] Number of Triangles Containing The Point (0,0)

问题描述

首先，对Topcoder的评分，因为这个问题在他们的一个SRM中被使用（但是它们没有编辑它）..

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

我已经尝试在堆栈上看这个线程：

围绕点的三角形点

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

一个明显的天真解决方案这个问题是使用无效的O（n ^ 3）算法并搜索所有的点。但是，有人可以帮助我提高效率，并在O（n ^ 2）时间做到这一点吗？

以下是Petr对这个问题的解决方案，这很简短，但是有一个很大的想法我不明白。

  / ** 
 *使用CHelper插件构建
 *实际解决方案位于顶部
 * / 
 public class TrianglesContainOrigin {
 public long count（int [] x，int [] y）{
 int n = x.length; 
 long res =（long）n *（n-1）*（n-2）/ 6; （int i = 0; i  int x0 = x [i]; 
 
 int y0 = y [i]; 
 long cnt = 0; （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 =（x_1，y_1）， p2 =（x_2，y_2）和 p3 =（x_3，y_3）。令p1，p2，p3为位置矢量。如果原点位于，则任何一个位置向量与其他两个位置矢量的交叉乘积在符号上不同（一个负，一个正）。但如果起源在外面，则会有一个点与其他点有负交叉积。所以对于每个点，我找到的交叉积小于0的点。现在如果你选择任意两个这些点，并与点i一起形成一个三角形，原点将在这个三角形的外面。这就是为什么你从res中减去（选择2从点+点i）。这是迄今为止最好的解决方案，因为它没有精度的双重问题。

First off, credits to Topcoder, as this problem was used in one of their SRMs (but they have no editorial for it..)

In this problem, I am given n points (where n is between 1 and 1000). For every three points, there is obviously a triangle that connects them. The question is, how many of these triangles contain the point (0,0).

I have tried looking at this thread on stack:

triangle points around a point

But I am unable to understand what data structures are used/how to use them to solve this problem.

An obvious naive solution to this problem is to use an inefficient O(n^3) algorithm and search all points. However, could someone please help me make this more efficient, and do this in O(n^2) time?

Below is Petr's solution to this problem... it is very short, but has a large idea I cannot understand.

/**
 * 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;
    }
}

解决方案

Let there be a triangle with 3 points p1=(x_1,y_1),p2=(x_2,y_2) and p3=(x_3,y_3). Let p1,p2,p3 be the position vectors.If origin lies within, then cross product of any one position vector with other two will be different in sign ( one negative , one positive ). But if origin lies outside then there will be one point which has negative cross product with both the other points. So for each point i find points whose cross product is less than 0.Now if you select any two of these points and make a triangle along with point i , origin will be outside this triangle.Thats why you subtract from res ( selection of 2 from such points + point i ). This was by far the best solution many implemented as it did not have the problem of precision with double etc.

这篇关于包含点的三角形数（0,0）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！