|
|
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=3706
  /**//*
 題意：
給定N(N <= 100000)個(gè)點(diǎn)，要求找到任意一個(gè)點(diǎn)的最近點(diǎn)，點(diǎn)的距離定義如下：
Distance (A, B) = max (|Ax – Bx|, |Ay – By|)，求出所有點(diǎn)的Distance和。
解法：
二維線段樹(shù)
思路：
我的做法是利用二維線段樹(shù)的二維區(qū)間求和，首先數(shù)字太大，需要離散化，然后
將所有數(shù)字插入到離散后的二維線段樹(shù)區(qū)間，二維線段樹(shù)維護(hù)一個(gè)Sum域，表示該二維
區(qū)間插入過(guò)的數(shù)字總和，然后對(duì)于每個(gè)點(diǎn)，二分枚舉和它最近的點(diǎn)的距離，根據(jù)這個(gè)
距離找到最大的被這個(gè)距離包含的并且在二維線段樹(shù)管轄范圍的二維區(qū)間，查詢(xún)那段
區(qū)間的Sum值，如果Sum值大于1的話說(shuō)明這個(gè)范圍不止一個(gè)點(diǎn)，于是可以縮小枚舉的范
圍，直到找到最小的枚舉值，就是這個(gè)點(diǎn)的最近點(diǎn)，總的復(fù)雜度O(nlog(n)log(n))。
這里需要注意的是，二維區(qū)間的Sum和統(tǒng)計(jì)和插入點(diǎn)的時(shí)候處理不好可能會(huì)在同一
區(qū)間插入多次或者統(tǒng)計(jì)多次，這和區(qū)間最值有所不同，需要特殊處理二維區(qū)間的某一維
的長(zhǎng)度為1的情況。
 */
 #include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define maxn 200010
#define eps 1e-6
#define maxaxis 1000000000
#define ll __int64
typedef int Type;
Type bin[maxn];
int size, tot;
int B(Type val)  {
int l = 0;
int r = tot-1;
  while(l <= r) {
int m = (l + r) >> 1;
if(bin[m] == val)
return m;
if(val > bin[m]) {
l = m + 1;
 }else
r = m - 1;
}
}
struct point {
int x, y;
int _ix, _iy;
}P[maxn];
struct Tree {
int son[4];
Type Sum;
void clear() {
Sum = 0;
for(int i = 0; i < 4; i++)
son[i] = -1;
}
}T[maxn*6];
int root, all;
void Insert(int& root, int x, int y, int lx, int rx, int ly, int ry) {
if(x > rx || x < lx || y > ry || y < ly)
return ;
if(root == -1) {
root = all++;
T[root].clear();
}
if(lx == rx && x == lx && y == ly && ly == ry) {
T[root].Sum ++;
return ;
}
int midx0 = (lx + rx) >> 1;
int midy0 = (ly + ry) >> 1;
int midx1 = (lx==rx) ? midx0 : midx0 + 1;
int midy1 = (ly==ry) ? midy0 : midy0 + 1;
if(lx == rx) {
Insert(T[root].son[0], x, y, lx, midx0, ly, midy0);
Insert(T[root].son[1], x, y, lx, midx0, midy1, ry);
}else if(ly == ry) {
Insert(T[root].son[1], x, y, lx, midx0, midy1, ry);
Insert(T[root].son[2], x, y, midx1, rx, ly, midy0);
}else {
Insert(T[root].son[0], x, y, lx, midx0, ly, midy0);
Insert(T[root].son[1], x, y, lx, midx0, midy1, ry);
Insert(T[root].son[2], x, y, midx1, rx, ly, midy0);
Insert(T[root].son[3], x, y, midx1, rx, midy1, ry);
}
int i;
T[root].Sum = 0;
for(i = 0; i < 4; i++) {
if(T[root].son[i] != -1) {
T[root].Sum += T[ T[root].son[i] ].Sum;
}
}
}
void Query(int root, int x0, int x1, int y0, int y1,
int lx, int rx, int ly, int ry, Type& Num) {
if(x0 > rx || x1 < lx || y0 > ry || y1 < ly || root == -1)
return ;
if(Num > 1)
return ;
if(x0 <= lx && rx <= x1 && y0 <= ly && ry <= y1) {
Num += T[root].Sum;
return ;
}
int midx0 = (lx + rx) >> 1;
int midy0 = (ly + ry) >> 1;
int midx1 = (lx==rx) ? midx0 : midx0 + 1;
int midy1 = (ly==ry) ? midy0 : midy0 + 1;
if(lx == rx) {
Query(T[root].son[0], x0, x1, y0, y1, lx, midx0, ly, midy0, Num);
Query(T[root].son[1], x0, x1, y0, y1, lx, midx0, midy1, ry, Num);
}else if(ly == ry) {
Query(T[root].son[1], x0, x1, y0, y1, lx, midx0, midy1, ry, Num);
Query(T[root].son[2], x0, x1, y0, y1, midx1, rx, ly, midy0, Num);
}else {
Query(T[root].son[0], x0, x1, y0, y1, lx, midx0, ly, midy0, Num);
Query(T[root].son[1], x0, x1, y0, y1, lx, midx0, midy1, ry, Num);
Query(T[root].son[2], x0, x1, y0, y1, midx1, rx, ly, midy0, Num);
Query(T[root].son[3], x0, x1, y0, y1, midx1, rx, midy1, ry, Num);
}
}
int LargeThan(int val, int pre) {
int l = 0;
int r = pre;
int ans = l;
while(l <= r) {
int m = (l + r) >> 1;
if(val <= bin[m]) {
r = m - 1;
ans = m;
}else
l = m + 1;
}
return ans;
}
int LessThan(int val, int pre) {
int l = pre;
int r = tot - 1;
int ans = r;
while(l <= r) {
int m = (l + r) >> 1;
if(val >= bin[m]) {
l = m + 1;
ans = m;
}else
r = m - 1;
}
return ans;
}
int Process(int idx, int dis) {
int xleft = LargeThan( P[idx].x - dis, P[idx]._ix );
int yleft = LargeThan( P[idx].y - dis, P[idx]._iy );
int xright = LessThan( P[idx].x + dis, P[idx]._ix );
int yright = LessThan( P[idx].y + dis, P[idx]._iy );
int Num = 0;
Query(root, xleft, xright, yleft, yright, 0, tot-1, 0, tot-1, Num);
return Num;
}
int n;
int main() {
int i;
int Max;
while(scanf("%d", &n) != EOF) {
size = 0;
tot = 0;
all = 0;
Max = 0;
for(i = 0; i < n; i++) {
scanf("%d %d", &P[i].x, &P[i].y);
bin[ size++ ] = P[i].x;
bin[ size++ ] = P[i].y;
if(P[i].x > Max) Max = P[i].x;
if(P[i].y > Max) Max = P[i].y;
}
sort(bin, bin + size);
for(i = 0; i < size; i++) {
if(i == 0 || bin[i] != bin[i-1])
bin[tot++] = bin[i];
}
root = -1;
for(i = 0; i < n; i++) {
P[i]._ix = B(P[i].x);
P[i]._iy = B(P[i].y);
Insert(root, P[i]._ix, P[i]._iy, 0, tot-1, 0, tot-1);
}
ll ans = 0;
for(i = 0; i < n; i++) {
int l = 0;
int r = Max;
int dis = 0;
while(l <= r) {
int m = (l + r) >> 1;
if(Process(i, m) > 1) {
r = m - 1;
dis = m;
}else
l = m + 1;
}
ans += dis;
}
printf("%I64d\n", ans);
}
return 0;
}
|