#P2380. rectangles

    ID: 1423 传统题 1000ms 512MiB 尝试: 18 已通过: 11 难度: 9 上传者: 标签>CF2600省选/NOI-有限候选集缩减离散化一维前缀和区间 DP二分图建模拟阵贪心Kuhn 算法

rectangles

题目描述

平面上给出 NN 个矩形。若一个矩形的四条边完全落在给定矩形的边界上,就称它为 cool 矩形。

为每个给定矩形各选一个 cool 矩形作为代表。代表必须完全位于对应矩形内,一个 cool 矩形只能代表一个给定矩形。选出的代表两两不得覆盖,边界可以重叠。

求所选代表的最小面积和。无解时输出 −1-1。

输入格式

第一行一个整数 NN。接下来是四行,每行 NN 个整数。第 ii 列依次给出第 ii 个矩形的一对对角顶点坐标 x1,y1,x2,y2x_1,y_1,x_2,y_2。

输出格式

输出最小面积和,无解则输出 −1-1。

样例 1

2
1 0
1 2
3 4
4 3
3

样例 2

2
0 1
0 1
2 3
2 3
-1

数据范围

对于 30%30\% 的数据,坐标绝对值不超过 100100。

对于所有数据,N≤30N\le30,坐标绝对值不超过 1000010000。

原 PDF 题面