Untitled

#define MAX_N 10001
#define MAX_NODE  40000 
#define DIVIDER 100
 
struct Rect {
    int id;
    int left, top, right, bottom;
    bool erased;
    int order;
 
    bool contains(int y, int x)
    {
        return top <= y && y <= bottom && left <= x && x <= right;
    }
 
    bool overlap(Rect* r)
    {
        return top <= r->bottom && bottom >= r->top && left <= r->right && right >= r->left;
    }
} rects[MAX_N];
int maxOrder;
 
Rect* newRect(int mID, int mY, int mX, int mHeight, int mWidth) 
{
    Rect* rect = &rects[mID];
    rect->id = mID;
    rect->left = mX;
    rect->top = mY;
    rect->right = mX + mWidth - 1;
    rect->bottom = mY + mHeight - 1;
    rect->order = ++maxOrder;
    rect->erased = false;
    return rect;
}
 
struct Node {
    Rect* rect;
    Node* prev;
    Node* next;
} nodePool[MAX_NODE];
int nodeCnt;
 
Node* newNode(Rect* rect)
{
    nodePool[nodeCnt].rect = rect;
    return &nodePool[nodeCnt++];
}
 
 
struct LinkedList {
    Node head;
    Node tail;
 
    void link(Node* n1, Node* n2)
    {
        n1->next = n2;
        n2->prev = n1;
    }
 
    void reset()
    {
        link(&head, &tail);
    }
 
    void add(Node* node)
    {
        Node* cur = head.next;
        while (cur != &tail && node->rect->order < cur->rect->order)
            cur = cur->next;
        link(cur->prev, node);
        link(node, cur);
    }
 
    Node* remove(Rect* rect) //find node that has rect and remove from linked list
    {
        for (Node* cur = head.next; cur != &tail; cur = cur->next) {
            if (cur->rect == rect) {
                link(cur->prev, cur->next);
                return cur;
            }
        }
        return nullptr;
    }   
 
    Rect* topOverlapRect() //find the highest rect that overlap with the rect on top (find from 2nd rect)
    {
        Rect* topRect = head.next->rect;
        for (Node* cur = head.next->next; cur != &tail; cur = cur->next) {
            if (!cur->rect->erased && topRect->overlap(cur->rect))
                return cur->rect;
        }
        return nullptr;
    }
} block[101][101];
 
void addRectToBlocks(Rect* rect) //add rect to all blocks that it cover
{
    int sY = rect->top / DIVIDER;
    int eY = rect->bottom / DIVIDER;
    int sX = rect->left/ DIVIDER;
    int eX = rect->right / DIVIDER;
 
    for (register int i = sY; i <= eY; i++)
        for (register int j = sX; j <= eX; j++) {
            Node* node = newNode(rect);
            block[i][j].add(node);
        }
}
 
Rect* findTopRect(int mY, int mX)
{
    int blockX = mX / DIVIDER;
    int blockY = mY / DIVIDER;
 
    Node* cur = block[blockY][blockX].head.next;
    while (cur != &block[blockY][blockX].tail) {
        if (!cur->rect->erased && cur->rect->contains(mY, mX))
            return cur->rect;
        cur = cur->next;
    }
    return nullptr;
}
 
 
void init(int N)
{
    nodeCnt = maxOrder = 0;
    int blockPerEdge = N / DIVIDER;
    for (register int i = 0; i <= blockPerEdge; i++)
        for (register int j = 0; j <= blockPerEdge; j++)
            block[i][j].reset();
}
 
void addRect(int mID, int mY, int mX, int mHeight, int mWidth)
{
    Rect* rect = newRect(mID, mY, mX, mHeight, mWidth);
    addRectToBlocks(rect);
}
 
void selectAndMove(int y1, int x1, int y2, int x2)
{
    Rect* rect = findTopRect(y1, x1);
    if (!rect)
        return;
 
    //Remove rectangle from all blocks that contains it
    int sY = rect->top / DIVIDER;
    int eY = rect->bottom / DIVIDER;
    int sX = rect->left/ DIVIDER;
    int eX = rect->right / DIVIDER;
    for (register int i = sY; i <= eY; i++)
        for (register int j = sX; j <= eX; j++) 
            block[i][j].remove(rect);
 
    //Update new coordinate for rectangle and add it into new blocks
    int height = rect->bottom - rect->top;
    int width = rect->right - rect->left;
    rect->left = x2;
    rect->top = y2;
    rect->right = x2 + width;
    rect->bottom = y2 + height;
    addRectToBlocks(rect);
}
 
int moveFront(int mID)
{
    Rect* rect = &rects[mID];
    if (rect->erased)
        return 0;
 
    rect->order = ++maxOrder;
    int sY = rect->top / DIVIDER;
    int eY = rect->bottom / DIVIDER;
    int sX = rect->left/ DIVIDER;
    int eX = rect->right / DIVIDER;
    for (register int i = sY; i <= eY; i++) {
        for (register int j = sX; j <= eX; j++) {
            Node* node = block[i][j].remove(rect);
            block[i][j].add(node);
        }
    }
 
    int topOrder = 0;
    int ret = 0;
    Rect* tmp;
    for (register int i = sY; i <= eY; i++) {
        for (register int j = sX; j <= eX; j++) {
            tmp = block[i][j].topOverlapRect();
            if (tmp && tmp->order > topOrder) {
                topOrder = tmp->order;
                ret = tmp->id;
            }
        }
    }
    return ret;
}
 
int selectAndErase(int mY, int mX)
{
    Rect* rect = findTopRect(mY, mX);
    if (!rect)
        return 0;
    rect->erased = true;
    return rect->id;
}
 
int check(int mY, int mX)
{
    Rect* rect = findTopRect(mY, mX);
    return rect ? rect->id : 0;
}