
USACO 2016 February Contest, Platinum
Problem 1. Load Balancing
Contest has ended.

Log in to allow submissions in analysis mode
Farmer John's $N$ cows are each standing at distinct locations
$(x_1, y_1) \ldots (x_n, y_n)$ on his two-dimensional farm
($1 \leq N \leq 100,000$, and the $x_i$'s and $y_i$'s are positive odd integers
of size at most $1,000,000$). FJ wants to partition his field by building a
long (effectively infinite-length) north-south fence with equation $x=a$ ($a$
will be an even integer, thus ensuring that he does not build the fence through
the position of any cow). He also wants to build a long (effectively
infinite-length) east-west fence with equation $y=b$, where $b$ is an even
integer. These two fences cross at the point $(a,b)$, and together they
partition his field into four regions.
Contest has ended. No further submissions allowed.
FJ wants to choose $a$ and $b$ so that the cows appearing in the four resulting regions are reasonably "balanced", with no region containing too many cows. Letting $M$ be the maximum number of cows appearing in one of the four regions, FJ wants to make $M$ as small as possible. Please help him determine this smallest possible value for $M$.
INPUT FORMAT (file balancing.in):
The first line of the input contains a single integer, $N$. The next $N$ lines each contain the location of a single cow, specifying its $x$ and $y$ coordinates.OUTPUT FORMAT (file balancing.out):
You should output the smallest possible value of $M$ that FJ can achieve by positioning his fences optimally.SAMPLE INPUT:
7 7 3 5 5 7 13 3 1 11 7 5 3 9 1
SAMPLE OUTPUT:
2
Problem credits: Brian Dean