Skip to content

14331: 【原4331】覆盖矩形

题目

题目描述

author: smallling 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4331

Description

给定$n$个矩形,每个矩形的边都平行于$x$轴或$y$轴,现在要用一个大矩形覆盖这$n$个矩形,求这个大矩形的最小面积(大矩形的边也要平行于$x$轴或$y$轴)。

Input Format

第一行一个数字$n$表示矩形个数。

接下来$n$行,第$i$行$4$个整数$x1_i,y1_i,x2_i,y2_i$,$(x1_i,y1_i)$表示矩形的左上角 ,$(x2_i,y2_i)$表示矩形的右下角。

$1 \leq n \leq 10^5$

$-10^4 \leq x1_i,y1_i,x2_i,y2_i \leq 10^4$

Output Format

一行一个数字表示答案

Sample Input

2
0 0 10 5
0 0 1 1

Sample Output

50

Hint

面积最小的大矩形为$((0, 0), (10, 5))$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!