1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
struct quad_tree
{
    int w, x, y;
    int a, b;
    int cnt;
    struct quad_tree *c[4];
};
struct quad_tree mem[50050];
int cnt;
void quad_insert(struct quad_tree *t, int x, int y)
{
    int i = 0, j = 0;
    t->cnt++;
    i = x < t->x + t->w / 2 ? 0 : 1;
    j = y < t->y + t->w / 2 ? 0 : 1;
    if(t->c[2 * i + j] == NULL)
    {
        struct quad_tree *n = &mem[cnt++];
        n->a = x;
        n->b = y;
        n->w = t->w >> 1;
        n->x = t->x + i * n->w;
        n->y = t->y + j * n->w;
        n->cnt = 1;
        t->c[2 * i + j] = n;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX