Untitled

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