3542316_ac_375ms_7768k.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;

public class Main {

	private Scanner in;
	private int area;
	private int n, xtot, ytot;
	private LinkedList <Rectangle> rectangle = new LinkedList <Rectangle> ();
	private boolean [][] covered;
	private int [] x;
	private int [] y;
	TreeSet <Integer> xset = new TreeSet <Integer> ();
	TreeSet <Integer> yset = new TreeSet <Integer> ();
	HashMap <Integer, Integer> xid = new HashMap <Integer, Integer> ();
	HashMap <Integer, Integer> yid = new HashMap <Integer, Integer> ();

	class Point {
		int x, y;
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
			xset.add(x);
			yset.add(y);
		}
	}

	class Rectangle {
		Point bl, tr;
		public Rectangle(Point bl, Point tr) {
			this.bl = bl;
			this.tr = tr;
		}
	}

	public static void main(String [] args) {
		new Main().run();
	}

	private void report() {
		while (true) {
			System.out.println("i love shengqi");
		}
	}

	private void run() {
		in = new Scanner (System.in);

		while (true) {
			int a, b, c, d;
			a = in.nextInt();b = in.nextInt();
			c = in.nextInt();d = in.nextInt();
			if (a == -1 && b == -1 && c == -1 && d == -1) {
				break;
			}
			xset.clear();
			yset.clear();
			xid.clear();
			yid.clear();
			rectangle.clear();
			rectangle.add(new Rectangle(new Point(a, b), new Point(c, d)));
			n = 1;
			while (true) {
				a = in.nextInt();b = in.nextInt();
				c = in.nextInt();d = in.nextInt();
				if (a == -1 && b == -1 && c == -1 && d == -1) {
					break;
				}
				rectangle.add(new Rectangle(new Point(a, b), new Point(c, d)));
				n++;
			}
			x = new int [n * 2];
			y = new int [n * 2];
			
				xtot = getId(xid, xset, x);
				ytot = getId(yid, yset, y);
			
			covered = new boolean [ytot + 1][xtot + 1];
			area = 0;
			for (Rectangle rec : rectangle) {
				int idbx = 0, idby = 0, idtx = 0, idty = 0;
				 idbx = xid.get(rec.bl.x);
				 idby = yid.get(rec.bl.y);
				 idtx = xid.get(rec.tr.x);
				 idty = yid.get(rec.tr.y);
				
				for (int i = idby; i < idty; i++) {
					for (int j = idbx; j < idtx; j++) {
						if (!covered[i][j]) {
							covered[i][j] = true;
							area += getArea(i, j);
							
						}
					}
				}
				
			}
			System.out.println(area);
			
		}
	}

	private int getArea(int i, int j) {
		return (x[j + 1] - x[j]) * (y[i + 1] - y[i]);
	}

	private int getId(HashMap <Integer, Integer> hm, TreeSet <Integer> ts, int [] array) {
		
		int cnt = 0;

		for (Integer d : ts) {
			array[cnt] = d;
			hm.put(d, cnt++);
		}
		return cnt;
	}
}