#PU619. USACO 2016 February Contest, Silver — Problem 2. Load Balancing

    ID: 1354 传统题 文件IO:balancing 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>USACO赛事:feb16来源:usaco.orgscoring:equal_test_cases二分

USACO 2016 February Contest, Silver — Problem 2. Load Balancing

USACO 2016 February Contest, Silver — Problem 2. Load Balancing

题目描述

Farmer John's NN cows are each standing at distinct locations (x1,y1)…(xn,yn)(x_1, y_1) \ldots (x_n, y_n) on his two-dimensional farm (1≤N≤10001 \leq N \leq 1000, and the xix_i's and yiy_i's are positive odd integers of size at most 1,000,0001,000,000). FJ wants to partition his field by building a long (effectively infinite-length) north-south fence with equation x=ax=a (aa 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=by=b, where bb is an even integer. These two fences cross at the point (a,b)(a,b), and together they partition his field into four regions. FJ wants to choose aa and bb so that the cows appearing in the four resulting regions are reasonably "balanced", with no region containing too many cows. Letting MM be the maximum number of cows appearing in one of the four regions, FJ wants to make MM as small as possible. Please help him determine this smallest possible value for MM.

输入格式

The first line of the input contains a single integer, NN. The next NN lines each contain the location of a single cow, specifying its xx and yy coordinates.

输出格式

You should output the smallest possible value of MM that FJ can achieve by positioning his fences optimally.

数据范围

(见题面原文)

样例

样例 1

7
7 3
5 5
7 13
3 1
11 7
5 3
9 1
2
Problem credits: Brian Dean