首页 > 试题广场 >

能否完美地拼成矩形

[编程题]能否完美地拼成矩形
  • 热度指数:523 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
每条边不是平行于X轴就是平行于Y轴的矩形,可以用左下角和右上角的点来表示。比如{1, 2, 3, 4},表示的图形如下

给定一个N行4列的二维数组matrix,表示N个每条边不是平行于X轴就是平行于Y轴的矩形。想知道所有的矩形能否组成一个大的完美矩形。完美矩形是指拼出的整体图案是矩形,既不缺任何块儿,也没有重合部分
[要求]
时间复杂度为,额外空间复杂度为

输入描述:
第一行一个整数N,表示matrix的行数
接下来N行,每行4个整数分别表示矩形的左下角和右上角的点


输出描述:
若可以拼成一个大的完美矩形,输出"Yes", 否则输出"No"
示例1

输入

4
1 1 3 3
3 1 4 2
1 3 2 4
3 2 4 4

输出

No

说明

缺少{2, 3, 3, 4}这一块儿
示例2

输入

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}是重合区域
示例3

输入

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

编辑于 2024-03-25 21:46:23 回复(0)

问题信息

上传者:小小
难度:
1条回答 3359浏览

热门推荐

通过挑战的用户

查看代码