某岛

… : "…アッカリ～ン . .. . " .. .

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("");
    }
}

….

Hash:

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神的代码