3470179_ac_516ms_4924k.java

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

import java.util.*;

public class Main {

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

	class Point {
		double x, y;
		public Point(double x, double 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 run() {
		in = new Scanner (System.in);
		int cas = 0;

		while (true) {
			n = in.nextInt();
			if (n == 0) {
				break;
			}
			cas++;
			System.out.println("Test case #" + cas);
			xset.clear();
			yset.clear();
			xid.clear();
			yid.clear();
			x = new double [n * 2];
			y = new double [n * 2];
			rectangle = new Rectangle [n];
			for (int i = 0; i < n; i++) {
				rectangle[i] = new Rectangle(new Point(in.nextDouble(), in.nextDouble())
					, new Point(in.nextDouble(), in.nextDouble()));
			}
			xtot = getId(xid, xset, x);
			ytot = getId(yid, yset, y);
			covered = new boolean [xtot + 1][ytot + 1];
			area = 0.0;
			for (Rectangle rec : rectangle) {
				int idbx = xid.get(rec.bl.x);
				int idby = yid.get(rec.bl.y);
				int idtx = xid.get(rec.tr.x);
				int 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.format("Total explored area: %.2f\n\n", area);
		}
	}

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

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

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