TopCoder SRM 641 Div. 1 250 - TrianglesContainOrigin

Problem Statement:
SRM 641 Div. 1 250 - TrianglesContainOrigin

Solution:
A pretty error prone computational geometry problem. The idea is actually quite simple, but the implementation can be quite tedious. Since no three points can form a collinear line, we can draw a line to each point P from the origin O and deterministically define that point by the angle defined by the line and the x-axis (that means the vector OP and the unit normal vector i of x-axis). Once we have converted every points as these angles and sort them, we can make use of another observation: if we choose two points with corresponding angles alpha and beta, then to form a triangle that contains the origin, we need to choose those points with angles between (alpha + 180, beta + 180). Otherwise, any triangle formed using points beyond these region will not contain the origin. This means that we can use binary search to find the number of points lying in the desired region. Overall we will have a \(O(N^2 \lg{N})\) running time complexity.