题目意思是给出平面上n个不相邻的点，要求到这n个点的曼哈顿距离之和最小的点的个数ans2，和这个最小距离ans1。
点的坐标范围是-10000到10000（这个很重要）
考虑到曼哈顿距离的定义：|x - x0| + |y - y0|
这个定义是线性的，对称的
因此考虑分别在两个方向上解这个问题（曼哈顿距离的性质）
1。对于x方向，定义x曼哈顿距离是|x - x0|，因为坐标范围很小，所以可以对所有可能的坐标，做一个线性扫描，求出fx，fx[x0]表示所有点到x0这个x坐标的x曼哈顿距离之和。对y方向相应地求出fy。
2。有了fx和fy，我们可以用O(1)时间算出所有点到某一坐标(x0, y0)的曼哈顿距离之和ans1。现在选出fx[x0] + fy[y0]的最小值（剔除那些输入的点），这一步我是把fx和fy分别排序做的，复杂度O(nlogn)。应该能利用点的不相邻性质做得更好。
3。现在统计满足题意的点的个数。利用fx计算数组nx，nx[i].coor表示此点的x坐标，nx[i].num表示x坐标是nx[i].coor的点的个数，nx[i].dist表示所有点到nx[i].coor的x曼哈顿距离之和。相应地计算ny。计算数组dd，dd[i]表示所有点到第i个点的曼哈顿距离之和。令t1 = sum(nx[i].num * ny[i].num), if (nx[i].dist + ny[i].dist == ans1)。令t2 = (dd[i] == ans1) 的个数。因此ans2 = t1 - t2。
下面是我的代码：
/**//*************************************************************************
Author: WHU_GCC
Created Time: 2008-1-19 20:26:13
File Name: pku3269.cpp
Description:
************************************************************************/
#include <iostream>
#include <set>
using namespace std;
#define out(x) (cout << #x << ": " << x << endl)
typedef long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) 
{ for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) { for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }
const int maxn = 10010;
struct node_t
{
int dist;
int coor;
};
struct num_t
{
int dist;
int num;
};
bool operator <(const node_t &a, const node_t &b)
{
return a.dist < b.dist;
}
int n;
int x[maxn];
int y[maxn];
node_t fx[maxn * 2];
node_t fy[maxn * 2];
int hx[maxn * 2];
int hy[maxn * 2];
int minx, miny, maxx, maxy;
int dd[maxn];
set <pair<int, int> > ptrset;
num_t nx[maxn];
num_t ny[maxn];
int lnx, lny;
int main()
{
scanf("%d", &n);
memset(hx, 0, sizeof(hx));
memset(hy, 0, sizeof(hy));
minx = miny = maxint;
maxx = maxy = 0;
ptrset.clear();
for (int i = 0; i < n; i++)
{
scanf("%d%d", &x[i], &y[i]);
x[i] += 10000;
y[i] += 10000;
ptrset.insert(make_pair(x[i], y[i]));
hx[x[i]]++;
hy[y[i]]++;
minx <?= x[i];
miny <?= y[i];
maxx >?= x[i];
maxy >?= y[i];
}
fx[minx].dist = 0;
fx[minx].coor = minx;
for (int i = minx + 1; i <= maxx; i++)
fx[minx].dist += abs(i - minx) * hx[i];
int numrx = n - hx[minx];
int nummx = hx[minx];
int numlx = 0;
for (int i = minx + 1; i <= maxx; i++)
{
fx[i].dist = fx[i - 1].dist + numlx + nummx - numrx;
fx[i].coor = i;
numlx += nummx;
nummx = hx[i];
numrx -= nummx;
}
fy[miny].dist = 0;
fy[miny].coor = miny;
for (int i = miny + 1; i <= maxy; i++)
fy[miny].dist += abs(i - miny) * hy[i];
int numry = n - hy[miny];
int nummy = hy[miny];
int numly = 0;
for (int i = miny + 1; i <= maxy; i++)
{
fy[i].dist = fy[i - 1].dist + numly + nummy - numry;
fy[i].coor = i;
numly += nummy;
nummy = hy[i];
numry -= nummy;
}
for (int i = 0; i < n; i++)
dd[i] = fx[x[i]].dist + fy[y[i]].dist;
sort(fx + minx, fx + maxx + 1);
sort(fy + miny, fy + maxy + 1);
int ans1;
for (int i = minx; i <= maxx; i++)
for (int j = miny; j <= maxy; j++)
{
if (ptrset.count(make_pair(fx[i].coor, fy[j].coor)) == 0)
{
ans1 = fx[i].dist + fy[j].dist;
goto end;
}
}
end:;
lnx = 0;
for (int i = minx; i <= maxx; i++)
{
if (i == minx)
{
nx[lnx].dist = fx[i].dist;
nx[lnx].num = 1;
lnx++;
}
else
{
if (fx[i].dist == nx[lnx - 1].dist)
nx[lnx - 1].num++;
else
{
nx[lnx].dist = fx[i].dist;
nx[lnx].num = 1;
lnx++;
}
}
}
lny = 0;
for (int i = miny; i <= maxy; i++)
{
if (i == miny)
{
ny[lny].dist = fy[i].dist;
ny[lny].num = 1;
lny++;
}
else
{
if (fy[i].dist == ny[lny - 1].dist)
ny[lny - 1].num++;
else
{
ny[lny].dist = fy[i].dist;
ny[lny].num = 1;
lny++;
}
}
}
int ans2 = 0;
for (int i = 0; i < lnx; i++)
if (nx[i].dist <= ans1)
{
for (int j = 0; j < lny; j++)
if (nx[i].dist + ny[j].dist <= ans1)
{
if (nx[i].dist + ny[j].dist == ans1)
ans2 += nx[i].num * ny[j].num;
}
else break;
}
else break;
for (int i = 0; i < n; i++)
if (dd[i] == ans1)
ans2--;
printf("%d %d\n", ans1, ans2);
return 0;
}