題目意思是給出平面上n個不相鄰的點(diǎn)，要求到這n個點(diǎn)的曼哈頓距離之和最小的點(diǎn)的個數(shù)ans2，和這個最小距離ans1。
點(diǎn)的坐標(biāo)范圍是-10000到10000（這個很重要）
考慮到曼哈頓距離的定義：|x - x0| + |y - y0|
這個定義是線性的，對稱的
因此考慮分別在兩個方向上解這個問題（曼哈頓距離的性質(zhì)）
1。對于x方向，定義x曼哈頓距離是|x - x0|，因為坐標(biāo)范圍很小，所以可以對所有可能的坐標(biāo)，做一個線性掃描，求出fx，fx[x0]表示所有點(diǎn)到x0這個x坐標(biāo)的x曼哈頓距離之和。對y方向相應(yīng)地求出fy。
2。有了fx和fy，我們可以用O(1)時間算出所有點(diǎn)到某一坐標(biāo)(x0, y0)的曼哈頓距離之和ans1。現(xiàn)在選出fx[x0] + fy[y0]的最小值（剔除那些輸入的點(diǎn)），這一步我是把fx和fy分別排序做的，復(fù)雜度O(nlogn)。應(yīng)該能利用點(diǎn)的不相鄰性質(zhì)做得更好。
3。現(xiàn)在統(tǒng)計滿足題意的點(diǎn)的個數(shù)。利用fx計算數(shù)組nx，nx[i].coor表示此點(diǎn)的x坐標(biāo)，nx[i].num表示x坐標(biāo)是nx[i].coor的點(diǎn)的個數(shù)，nx[i].dist表示所有點(diǎn)到nx[i].coor的x曼哈頓距離之和。相應(yīng)地計算ny。計算數(shù)組dd，dd[i]表示所有點(diǎn)到第i個點(diǎn)的曼哈頓距離之和。令t1 = sum(nx[i].num * ny[i].num), if (nx[i].dist + ny[i].dist == ans1)。令t2 = (dd[i] == ans1) 的個數(shù)。因此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;
}