The number of triangles containing a point (0,0)

Question

Firstly, Topcoder loans, since this problem was used in one of their SRMs (but they don’t have an editorial for it ..)

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

I tried to look at this thread on the stack:

a triangle points around a point

But I can’t understand what data structures are used / how to use them to solve this problem.

An obvious naive solution to this problem is to use the inefficient O (n ^ 3) algorithm and search for all points. However, can someone please help me make it more efficient and do it O (n ^ 2) times?

Below is Peter's decision on this problem ... it is very short, but has a big idea that 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;
    }
}

Answer 1

Let there be a triangle with three points p1 = (x_1, y_1) , p2 = (x_2, y_2) and p3 = (x_3, y_3). p1, p2, p3 - . , ( , ). , , . , - 0. , i, . res ( 2 + i). , , , , ..