# 某島

… : "…アッカリ～ン . .. . " .. .
February 28, 2012

## URAL 1369. Cockroach Race

### Brief description:

（點集規模 N <= 100000, 詢問次數 M <= 10000)

### Analysis:

.. .

#### Naive:

const int N = 100009;

Po P[N], cur;
int n, m;

int main() {

//freopen("in.txt", "r", stdin);

REP_C(i, _RD(n)){
scanf("%lf %lf", &P[i].x, &P[i].y);
}

DO_C(RD()){
scanf("%lf %lf", &cur.x, &cur.y);
DB d = INF; REP(i, n) checkMin(d, dist_sqr(cur, P[i]));
REP(i, n) if (d == dist_sqr(cur, P[i]))
printf("%d ", i + 1);
puts("");
}
}


….




#### Data Structure:

...
int random(int l, int r){
return rand() % (r - l + 1) + l;
}

struct Rec: Po{
int id;
};

const int N = 100009;
const int NN = N;

/*
|
1|0
-----
3|2
|
*/

Rec node[NN]; DB xl[NN], xr[NN], yl[NN], yr[NN]; int c[NN][4], root, total;
// Point Quadtree .. .

Rec P[N], temp; Po cur; DB d; VI L;
int n, m;

inline int Dir(Po a, Po b){
return a.x < b.x ? (a.y < b.y ? 3 : 1) : (a.y < b.y ? 2 : 0);
}

inline int Rev(int dir){
return dir ^ 3;
}

void Insert(int &now = root){
if (!now) now = ++total, node[now] = temp;
else Insert(c[now][Dir(temp, node[now])]);
}

void Cut(int now, int parent){
if (!now) return;

if (node[now].x < node[parent].x) xl[now] = xl[parent], xr[now] = node[parent].x; else xl[now] = node[parent].x, xr[now] = xr[parent];
if (node[now].y < node[parent].y) yl[now] = yl[parent], yr[now] = node[parent].y; else yl[now] = node[parent].y, yr[now] = yr[parent];
REP(i, 4) Cut(c[now][i], now);
}

void Update(Rec item){

DB dd = dist_sqr(cur, item);

if (sgn(dd, d) <= 0){
if (sgn(dd, d) == -1) d = dd, CLR(L);
L.PB(item.id);
}
}

void Find(int now = root){

if (!now) return;

if (xl[now] <= cur.x && cur.x <= xr[now]){
if (cur.y <= yl[now]) if (sgn(d, sqr(yl[now] - cur.y)) < 0) return;
if (yr[now] <= cur.y) if (sgn(d, sqr(cur.y - yr[now])) < 0) return;
}
else if (yl[now] <= cur.y && cur.y <= yr[now]){
if (cur.x <= xl[now]) if (sgn(d, sqr(xl[now] - cur.x)) < 0) return;
if (xr[now] <= cur.x) if (sgn(d, sqr(cur.x - xr[now])) < 0) return;
}
else if (sgn(d, min(sqr(xl[now] - cur.x), sqr(xr[now] - cur.x)) + min(sqr(yl[now] - cur.y), sqr(yr[now] - cur.y))) < 0) return;

int dir = Dir(cur, node[now]);
Find(c[now][dir]), Update(node[now]);
if (dir == 0 || dir == 3) Find(c[now][1]), Find(c[now][2]);
else if (dir == 1 || dir == 2) Find(c[now][0]), Find(c[now][3]);
}

int main() {

//freopen("in.txt", "r", stdin);

REP_C(i, _RD(n)){
scanf("%lf %lf", &P[i].x, &P[i].y);
P[i].id = i + 1;
}

srand((unsigned)time(NULL)); REP(i, n) swap(P[i], P[random(i, n - 1)]);
REP(i, n) temp = P[i], Insert();

xl[root] = yl[root] = -10000, xr[root] = yr[root] = 10000;
REP(i, 4) Cut(c[root][i], root);

DO_C(RD()){
scanf("%lf %lf", &cur.x, &cur.y), CLR(L), d = INF; Find();
SRT(L); REP(i, SZ(L) - 1) printf("%d ", L[i]);
printf("%d\n", L[SZ(L)-1]);
}
}


...
int random(int l, int r){
return rand() % (r - l + 1) + l;
}

struct Rec: Po{
int id;
};

const int N = 100009;
const int NN = N;

Rec node[NN]; DB xl[NN], xr[NN], yl[NN], yr[NN];
int c[NN][2], root, total;
// 2-d tree .. .

Rec P[N], temp; Po cur; DB d; VI L;
int n, m;

inline int Dir(int level, Po a, Po b){
if (level&1) return a.x < b.x ? 0 : 1;
else return a.y < b.y ? 0 : 1;
}

inline int Rev(int dir){
return dir ^ 1;
}

void Insert(int &now = root, int level = 0){
if (!now) now = ++total, node[now] = temp;
else Insert(c[now][Dir(level, temp, node[now])], level + 1);
}

void Cut(int now, int parent, int level){
if (!now) return;

if (level&1){
if (node[now].x < node[parent].x) xl[now] = xl[parent], xr[now] = node[parent].x; else xl[now] = node[parent].x, xr[now] = xr[parent];
yl[now] = yl[parent], yr[now] = yr[parent];
}
else {
if (node[now].y < node[parent].y) yl[now] = yl[parent], yr[now] = node[parent].y; else yl[now] = node[parent].y, yr[now] = yr[parent];
xl[now] = xl[parent], xr[now] = xr[parent];
}

REP(i, 2) Cut(c[now][i], now, level + 1);
}

void Update(Rec item){

DB dd = dist_sqr(cur, item);

if (sgn(dd, d) <= 0){
if (sgn(dd, d) == -1) d = dd, CLR(L);
L.PB(item.id);
}
}

void Find(int now = root, int level = 0){

if (!now || sgn(d, ((xl[now] <= cur.x && cur.x <= xr[now]) ? 0. : min(sqr(cur.x - xl[now]), sqr(cur.x - xr[now]))) + ((yl[now] <= cur.y && cur.y <= yr[now]) ? 0. : min(sqr(cur.y - yl[now]), sqr(cur.y - yr[now])))) < 0) return;

int dir = Dir(level, cur, node[now]); Find(c[now][dir], level + 1), Update(node[now]); Find(c[now][Rev(dir)], level + 1);
}

int main() {

//freopen("in.txt", "r", stdin);

REP_C(i, _RD(n)){
scanf("%lf %lf", &P[i].x, &P[i].y);
P[i].id = i + 1;
}

//srand((unsigned)time(NULL)); REP(i, n) swap(P[i], P[random(i, n - 1)]);
REP(i, n) temp = P[i], Insert();

xl[root] = yl[root] = -10000, xr[root] = yr[root] = 10000;
REP(i, 2) Cut(c[root][i], root, 0);

DO_C(RD()){
scanf("%lf %lf", &cur.x, &cur.y), CLR(L), d = INF; Find();
SRT(L); REP(i, SZ(L) - 1) printf("%d ", L[i]);
printf("%d\n", L[SZ(L)-1]);
}
}


try神的代碼

### Reference:

The Design and Analysis of Spatial Data Structures[Hanan][Samet]