PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
First, let’s solve the following subproblem. Suppose we’ve already distributed the vertices of the graph among the quadrants. What is the smallest possible number of intersections then? Obviously, each edge connecting two vertices from differents quadrants produces at least one intersection. But notice that at least is actually at most – we can place each vertex so that the absolute values of its X and Y coordinates are equal. This way every edge connecting the 1st and the 3rd (or the 2nd and the 4th) quadrants will pass through the origin, resulting in just one intersection for us. Of course, the graph won’t look good any more, but recall that Caroline doesn’t care about that 
Now on to the problem. Instead of minimizing the number of edges connecting vertices from different quadrants, let’s maximize the number of edges connecting vertices from the same quadrant (that’s essentially the same; we’ll call such edges inner). The only question remaining is the optimal distribution of vertices among the quadrants. Simply trying every possible distribution won’t finish in time – there are 192 972 780 different distributions into subsets of 4, 4, 5 and 5 vertices in the worst case of N = 18.
Let’s iterate over all possible sets of N/2 vertices (recall that N is even) and find the best (with maximal number of inner edges) distribution of these vertices between two quadrants simply checking every possible distribution. For N = 18 we have 48 620 subsets of size 9 and 126 possible separations of 9 vertices into 4 and 5, giving a total of 6 126 120 combinations – considerably less than 192 million. Then, let’s iterate over all possible separations of the given N vertices into two subsets of size N/2. As for either subset we already know the best distribution between two quadrants, we can just add the numbers of inner edges for both subsets to get the number of inner edges in the best overall distribution.
This approach is of course faster than the trivial one, but it is still too slow if we count the number of inner edges improperly. The fastest way to do it is to use bitmasks. We can build a bitmask Ti for each vertex with set bits (that is, 1-bits) corresponding to the vertices connected with it. If we want now to find out how many edges connect vertex i with vertices of some fixed subset represented by bitmask B, we can just find the number of set bits in B & Ti, where & is bitwise AND operation. The number of set bits can be easily precalculated for each possible mask beforehand. Solutions using this approach were supposed to get accepted though they might have needed some optimization.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.