每条边不是平行于X轴就是平行于Y轴的矩形,可以用左下角和右上角的点来表示。比如{1, 2, 3, 4},表示的图形如下
给定一个N行4列的二维数组matrix,表示N个每条边不是平行于X轴就是平行于Y轴的矩形。想知道所有的矩形能否组成一个大的完美矩形。完美矩形是指拼出的整体图案是矩形,既不缺任何块儿,也没有重合部分
[要求]
时间复杂度为,额外空间复杂度为
第一行一个整数N,表示matrix的行数
接下来N行,每行4个整数分别表示矩形的左下角和右上角的点
若可以拼成一个大的完美矩形,输出"Yes", 否则输出"No"
4 1 1 3 3 3 1 4 2 1 3 2 4 3 2 4 4
No
缺少{2, 3, 3, 4}这一块儿
5 1 1 3 3 3 2 4 3 3 2 4 4 1 3 2 4 2 3 3 4
No
拼出的图案缺少{3, 1, 4, 2},并且{3, 2, 4, 2}是重合区域
5 1 1 3 3 3 1 4 2 3 2 4 4 1 3 2 4 2 3 3 4
Yes
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.Set; import java.util.HashSet; import java.util.Objects; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); Set<Point> counter = new HashSet<>(); int mostDownX = Integer.MAX_VALUE; int mostDownY = Integer.MAX_VALUE; int mostUpX = Integer.MIN_VALUE; int mostUpY = Integer.MIN_VALUE; int sumOfArea = 0; for (int i = 0; i < n; i ++) { String[] strs = br.readLine().split(" "); int x1 = Integer.parseInt(strs[0]); int y1 = Integer.parseInt(strs[1]); int x2 = Integer.parseInt(strs[2]); int y2 = Integer.parseInt(strs[3]); mostDownX = Math.min(mostDownX, x1); mostDownY = Math.min(mostDownY, y1); mostUpX = Math.max(mostUpX, x2); mostUpY = Math.max(mostUpY, y2); sumOfArea += (x2 - x1) * (y2 - y1); Point leftDown = new Point(x1, y1); if (!counter.add(leftDown)) { counter.remove(leftDown); } Point leftUp = new Point(x1, y2); if (!counter.add(leftUp)) { counter.remove(leftUp); } Point rightDown = new Point(x2, y1); if (!counter.add(rightDown)) { counter.remove(rightDown); } Point rightUp = new Point(x2, y2); if (!counter.add(rightUp)) { counter.remove(rightUp); } } // 拼成矩形的四个顶点,需要且只能出现 1 次 if (!counter.contains(new Point(mostDownX, mostDownY)) || !counter.contains(new Point(mostDownX, mostUpY)) || !counter.contains(new Point(mostUpX, mostUpY)) || !counter.contains(new Point(mostUpX, mostDownY)) || counter.size() != 4) { System.out.println("No"); return; } if (sumOfArea == (mostUpX - mostDownX) * (mostUpY - mostDownY)) { System.out.println("Yes"); } else { System.out.println("No"); } } } class Point { int x; int y; public Point(int x, int y) { this.x = x; this.y = y; } @Override public boolean equals(Object obj) { if (this == obj) { return true; } if (obj == null || getClass() != obj.getClass()) { return false; } Point that = (Point) obj; return x == that.x && y == that.y; } @Override public int hashCode() { return Objects.hash(x) ^ Objects.hash(y); } }