Untitled
unknown
plain_text
a year ago
5.3 kB
0
Indexable
Never
#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; }