Problem D
Fair Divisions

Lily and Severus discovered very special magical plants that glowed in the dark in the field behind their favorite playground. The children greatly admired the plants and loved to sit in the field, watch the plants, and chat to each other. Until one day, a quarrel (something about a branch falling on Lily’s sister’s head) set them apart. They still wanted to sit in the field and admire the plants but they did not want to look at each other. They were not eleven yet but already had plenty of magical abilities. In particular, they knew how to make a long, straight, tall, and very thin impenetrable barrier appear wherever they wanted. They, despite being upset with each other, had a keen sense of fairness, so they decided to split the plants evenly between them and separate Lily’s plants from Severus’s plants by an impenetrable barrier. At some point it dawned on the children that it is better to work through their disagreements, so they decided not to go through with the plan after all. But they became very curious about finding the number of possible such fair divisions of the plants, that is, the number of ways in which they could split the plants evenly so that a straight impenetrable barrier could separate the two sets of plants.


The first line contains a positive integer $n$, the number of plants. Then $n$ lines follow. The $i$-th line contains the coordinates $x_ i$ and $y_ i$ of the $i$-th plant. (These plants are very magical: each plant occupies a single point in the plane.) You may assume that $n\leq 2\, 000$ and that the coordinates are integers with absolute value at most $10\, 000$. You may also assume that no two plants are at the same location.


The output contains one line with the number of possible ways to split the plants between Lily and Severus. In particular, in how many ways can we split the plants, so that Lily and Severus each get half of all the plants, and it is possible to separate Lily’s plants from Severus’s plants by a single line in the plane (that does not pass through any of the plants)?

As an example, here are all the corresponding fair divisions for the sample input given below (Lily’s plants are shown in red, Severus’s in blue; each figure also shows a possible barrier):

\includegraphics[width=0.25\textwidth ]{sample1FairDivisions}

\includegraphics[width=0.25\textwidth ]{sample1FairDivisions_case1} \includegraphics[width=0.25\textwidth ]{sample1FairDivisions_case2} \includegraphics[width=0.25\textwidth ]{sample1FairDivisions_case3}

\includegraphics[width=0.25\textwidth ]{sample1FairDivisions_case4} \includegraphics[width=0.25\textwidth ]{sample1FairDivisions_case5} \includegraphics[width=0.25\textwidth ]{sample1FairDivisions_case6}

Sample Input 1 Sample Output 1
0 0
2 0
3 2
4 3
2 3
2 4

Please log in to submit a solution to this problem

Log in