yaro's blog

By yaro, 9 years ago, translation, , Let us solve this problem for every point P independently. We will show how to do this in linear time, that is, O(N). It seems that the most easy way to do this is to count the number of triangles not containing P (call them good), and then subtract this value from the total number of triangles.

Consider triples of vertices A, B, C that form a triangle, such that: P doesn't lie in ABC; AB separates P and C in the polygon; P lies in the polygon to the right from AB (clockwise). Note, that every good triangle provides us one such triple and each triple forms a good triangle. Thus, we may consider such triples instead of good triangles.

Let's consider an arbitrary vertex of the polygon. We want it to become an A-vertex in some triple. Then we can obtain the set of vertices, suitable for B-vertex in a triple moving diagonals from A (clockwise) until we reach P. Then for the fixed A the number of triples is equal to the sum of the number of triples for this A and the fixed B, which is equal to the sum of some linear series (as all suitable C lie between A and B and their number is equal to the vertex-distance between A and B minus one).

The only thing left to do is to find the last B (last until P is reached) for each vertex of the polygon. And this is a simple exercise on the two pointers technique. Tutorial of Codeforces Beta Round #51 Tutorial of Codeforces Beta Round #51  Comments (1)
 Thanks for solutions.