# BALANPOL - Editorial

Author: Praveen Dhinwa
Tester: Animesh Fatehpuria
Editorialist: Pawel Kacprzak

MEDIUM

Geometry, dp

### PROBLEM:

For a given convex polygon with N vertices and M additional points on a plane, where each of them is colored either red or blue, the goal is to find the number of subsets of N vertices of the polygon, such that each of these subsets describes a convex polygon with equal number of red and blue points inside it (or on its boundary).

### EXPLANATION:

One crucial fact used basically in all approaches described below is that any subset of vertices of a convex polygon describes also a convex polygon. Here we define a polygon to be described by some points as a polygon described by them in an anticlockwise order.

The problem has also an additional difficulty: notice that two or more colored points in the input can share the same coordinates.

A very useful subroutine in this problem is the ability of checking if a given point is inside a convex polygon. This case is easier than checking this for any polygon, and a very efficient method of doing it is described here: How to test if a point is inside of a convex polygon in 2D integer coordinates?.

In the first subtask both N, M \leq 12, so it is possible to generate all possible subsets of these N points, and then for each of these subsets iterate over all M colored points and count the number of blue and red points inside the polygon formed by the selected subset. If these two amounts are equal, just add 1 to the result.

In the second subtask, N and M can be both up to 50, but we know that all colored points have different coordinates and that all them lie on the vertices of the input polygon. In this case the problem is not hard at all. Let’s say that we want to count the number of valid choices of exactly k vertices of the polygon corresponding to chosen k blue points and exactly k other vertices of the polygon corresponding to the chosen k red points. The first thing to notice is that every such choice describes a valid convex polygon with exactly k blue and k red points in it (well, exactly on it’s boundary), and no two different ways of choosing such points produces the same polygon, and also there are 2^W ways to choose vertices not sharing coordinates with any colored points, where W is the number of such vertices. Thus the total number of valid polygons containing exactly k blue and exactly k red points is given by \binom{B}{k} \cdot \binom{R}{k} \cdot 2^W, where B is the total number of blue points and R is the total number of red points. In order to get the final answer, it is sufficient to return the sum of such sub-results computed for all possible k from 2 to \min(B, R).