2753. Building A New Barn
Time Limit: 1.0 Seconds Memory Limit: 65536K
Total Runs: 126 Accepted Runs: 36 Multiple test files
After scrimping and saving for years, Farmer John has decided to
build a new barn. He wants the barn to be highly accessible, and
he knows the coordinates of the grazing spots of all N (2 ≤ N ≤
10,000) cows. Each grazing spot is at a point with integer coordinates
(Xi , Yi) (-10,000 ≤ Xi ≤ 10,000;
-10,000 ≤ Yi ≤ 10,000).
The hungry cows never graze in spots that are horizontally or
vertically adjacent.
The barn must be placed at integer coordinates and cannot be on any
cow's grazing spot. The inconvenience of the barn for any cow is
given the Manhattan distance formula |X-Xi|+|Y-Yi|, where (X , Y)
and (Xi , Yi) are the coordinates of the barn and the cow's grazing
spot, respectively. Where should the barn be constructed in order
to minimize the sum of its inconvenience for all the cows?
Input
* Line 1: A single integer: N
* Lines 2..N + 1: Line i + 1 contains two space-separated integers which
are the grazing location (Xi , Yi) of cow i
Output
* Line 1: Two space-separated integers: the minimum inconvenience for
the barn and the number of spots on which Farmer John can
build the barn to achieve this minimum.
Sample Input
4
1 -3
0 1
-2 1
1 -1
Sample Output
10 4
Input Details
The field contains 4 cows with grazing spots at the points (1, -3),
(0, 1), (-2, 1), and (1, -1).
Output Details
The minimum inconvenience is 10, and there are 4 spots that Farmer John can
build the farm to achieve this: (0, -1), (0, 0), (1, 0), and (1, 1).
Source: USACO 2007 February Competition
Submit List
Runs Forum Statistics
Tianjin University Online Judge v1.2.4