← 返回题目列表

Codeforces · 335/D

D. 矩形和正方形

中文机器翻译题面 查看原题

给定 n 个矩形,标记为 1 到 n。矩形的角具有整数坐标,它们的边平行于 Ox 和 Oy 轴。矩形可能彼此接触,但它们不重叠(即,不存在属于多个矩形内部的点)。

您的任务是确定是否存在形成正方形的矩形的非空子集。即,确定是否存在矩形和某个正方形的子集,其中属于该正方形的内部或边界的每个点都属于该子集中的至少一个矩形的内部或边界,并且属于该子集中的至少一个矩形的内部或边界的每个点都属于该正方形的内部或边界。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105) — 矩形的数量。接下来的 n 行中的每一行都包含对矩形的描述,其中第 i 行描述了标记为 i 的矩形。每个矩形描述由四个整数组成:x1、y1、x2、y2 — 左下角和右上角的坐标(0 ≤ x1 < x2 ≤ 3000、0 ≤ y1 < y2 ≤ 3000)。

没有两个矩形重叠(即没有点属于多个矩形的内部)。

输出

如果存在这样的子集,则在输出文件的第一行打印“YES”(不带引号),后跟 k,即子集中矩形的数量。在第二行打印 k 个数字——子集中矩形的标签,按任意顺序排列。如果存在多个这样的子集,则打印任何一个。如果不存在这样的子集,则打印“NO”(不带引号)。

示例

输入 #1

9
0 0 1 9
1 0 9 1
1 8 9 9
8 1 9 8
2 2 3 6
3 2 7 3
2 6 7 7
5 3 7 6
3 3 5 6

输出 #1

YES 5
5 6 7 8 9

输入 #2

4
0 0 1 9
1 0 9 1
1 8 9 9
8 1 9 8

输出 #2

NO

注意

第一个测试用例如下所示:

请注意,矩形 6、8 和 9 也形成正方形,并且是一个可接受的答案。

第二个测试用例如下所示: