【bzoj1696】[Usaco2007 Feb]Building A New Barn新牛舍

2014年3月26日1,1450

Description

经过多年的积蓄,农夫JOHN决定造一个新的牛舍。他知道所有N(2 <= N <= 10,000)头牛的吃草位置,所以他想把牛舍造在最方便的地方。 每一头牛吃草的位置是一个整数点(X_i, Y_i) (-10,000 <= X_i <= 10,000; -10,000 <= Y_i <= 10,000)。 没有两头牛的吃草位置是相邻的。 JOHN决定把牛舍造在一个没有牛吃草的整数点上。如果牛舍在(X, Y),在(X_i, Y_i)的牛到牛舍的距离是|X-X_i|+|Y-Y_i|。 JOHN把牛舍造在哪儿才能使所有牛到牛舍的距离和最低?

Input

第1行: 一个数,N。

第2~N+1行:第i+1行 包含第i头牛的位置(X_i, Y_i)。

Output

第1行: 两个数,最小距离和和所有可能达到这个距离和的牛舍位置的数目。

Sample Input

4
1 -3
0 1
-2 1
1 -1

输入解释:

一共有4头牛,位置分别为(1, -3), (0, 1), (-2, 1), 和(1, -1).

Sample Output

10 4

输出解释:
最小距离和是10,可以在牛舍位于 (0, -1), (0, 0), (1, 0), (1, 1)时达到。

题解

    当n是偶数时,([x[n / 2 – 1], x[n / 2]], [y[n / 2 – 1], y[n / 2]])中的点为满足的P点,可以相应的求出距离和sum值,cnt = (x[n / 2] – x[n / 2 – 1] + 1) * (y[n / 2] – y[n / 2 – 1] + 1) – exist(x[n / 2], y[n / 2 – 1]) – exist(x[n / 2], y[n / 2] – exist(x[n / 2 – 1], y[n / 2 – 1]) – exist(x[n / 2 – 1], y[n / 2]).(其中exist返回点x[], y[]是否在n个点中,返回值为0或1,且exist()中的点必须不同)

    当n是奇数时,

如果exist(x[n / 2], y[n / 2])是不在pt[]点中的话,(x[n / 2], y[n / 2])即为p点,且只有1个,再相应的统计出sum值。

否则,取点(x[n / 2] – 1, y[n / 2]), (x[n / 2] + 1, y[n / 2]),(x[n / 2], y[n / 2 – 1]),(x[n / 2], y[n / 2] + 1)进行统计,得出最优解。