CODEWITHSUNDEEP
algorithmdata-structures
user3904840
user3904840

Reputation: 169

Number of Triangles Containing The Point (0,0)

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

Upvotes: 3

Views: 1096

Answers (1)

advocateofnone
advocateofnone

Reputation: 2541

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 the 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 the 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, the origin will be outside this triangle. That's 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. enter image description here

Upvotes: 5

Related Questions