#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;
}