package Rectangle_Manager;
class Rect {
int id;
int left, top, right, bottom;
boolean erased;
int order;
boolean contains(int y, int x) {
if (top <= y && y <= bottom && left <= x && x < right) {
return true;
}
return false;
}
boolean overlap(Rect r) {
if (top <= r.bottom && bottom >= r.top && left < r.right
&& right >= r.left) {
return true;
}
return false;
}
}
class Node {
Rect rect;
Node prev;
Node next;
}
class Linkedlist {
Node head;
Node tail;
public Linkedlist() {
super();
this.head = new Node();
this.tail = new Node();
connect(head, tail);
}
void connect(Node n1, Node n2) {
n1.next = n2;
n2.prev = n1;
}
void reset() {
connect(head, tail);
}
boolean isEmpty() {
return head.next == tail;
}
void addNode(Node node) {
Node cur = head.next;
while (cur!=tail && node.rect.order < cur.rect.order) {
cur = cur.next;
}
connect(cur.prev, node);
connect(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) {
connect(cur.prev, cur.next);
return cur;
}
}
return null;
}
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 null;
}
}
class UserSolution {
private static final int MAX_N = 10001;
private static final int MAX_NODE = 40000;
private static final int DIVIDER = 100;
int maxOrder;
Rect[] rects;
int nodecnt;
Node[] nodePool;
Linkedlist[][] block;
Rect newRect(int mID, int mY, int mX, int mHeight, int mWidth) {
Rect rect = new Rect();
rects[mID] = rect;
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;
}
Node newNode(Rect rect) {
Node node = new Node();
node.rect = rect;
nodePool[nodecnt] = node;
nodecnt++;
return node;
}
void addRectToBlock(Rect rect) {
int sY = rect.top / DIVIDER;
int eY = rect.bottom / DIVIDER;
int sX = rect.left / DIVIDER;
int eX = rect.right / DIVIDER;
for (int i = sY; i <= eY; i++) {
for (int j = sX; j <= eX; j++) {
Node node = newNode(rect);
if (block[i][j] == null) {
block[i][j] = new Linkedlist();
}
block[i][j].addNode(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 null;
}
void init(int N) {
maxOrder = 0;
nodecnt = 0;
rects = new Rect[MAX_N];
nodePool = new Node[MAX_NODE];
block = new Linkedlist[101][101];
int blockPerEdge = N / DIVIDER;
for ( int i = 0; i <= blockPerEdge; i++)
for ( int j = 0; j <= blockPerEdge; j++)
block[i][j]=new Linkedlist();
}
void addRect(int mID, int mY, int mX, int mHeight, int mWidth) {
Rect rect = newRect(mID, mY, mX, mHeight, mWidth);
addRectToBlock(rect);
}
void selectAndMove(int y1, int x1, int y2, int x2) {
Rect rect = findTopRect(y1, x1);
if (rect == null)
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 (int i = sY; i <= eY; i++)
for (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;
addRectToBlock(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 (int i = sY; i <= eY; i++) {
for (int j = sX; j <= eX; j++) {
Node node = block[i][j].remove(rect);
block[i][j].addNode(node);
}
}
int topOrder = 0;
int ret = 0;
Rect tmp;
for (int i = sY; i <= eY; i++) {
for (int j = sX; j <= eX; j++) {
tmp = block[i][j].topOverlapRect();
if (tmp != null && tmp.order > topOrder) {
topOrder = tmp.order;
ret = tmp.id;
}
}
}
return ret;
}
int selectAndErase(int mY, int mX) {
Rect rect = findTopRect(mY, mX);
if (rect == null)
return 0;
rect.erased = true;
return rect.id;
}
int check(int mY, int mX) {
Rect rect = findTopRect(mY, mX);
if (rect == null) {
return 0;
}
return rect.id;
}
}