← 返回题目列表

Codeforces · 1181/E1

E1. 一个国家的故事(简单)

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

这个问题与下一个问题的区别仅在于约束。

Petya 决定在暑假期间参观 Byteland。原来,这个国家的历史颇不寻常。

最初,现在伯兰的土地上有 $$$n$$$ 个不同的国家。每个国家都有自己的领土,在地图上用矩形表示。矩形的边与轴平行,角位于具有整数坐标的点处。两个国家的领土没有相交,但有些领土可能相互接触。随着时间的推移,有时两个国家会合并为一个国家。只有当他们的领土联合起来也是一个矩形时才会发生这种情况。最终只剩下一个国家——拜特兰。

最初,每个国家在其领土内都有一座长方形的城堡。它的边平行于轴,它的角有整数坐标。有些城堡可能会触及相应国家和侧面或其他城堡的边界。奇迹般的是,在所有的联合之后,城堡仍然完好无损。不幸的是,他们的位置是我们恢复这些国家最初领土的唯一信息。

Byteland 的可能形成。城堡以蓝色显示。

Petya 想知道为什么没有关于最初国家的信息。他怀疑整个故事都是假的。你被推荐给他作为一个聪明人。请检查是否存在一组可能的初始领土可以使故事成真。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 1000$$$) — 国家和城堡的数量。

接下来的 $$$n$$$ 行包含四个整数 $$$a_i, b_i, c_i, d_i$$$ ($$$0 \leq a_i < c_i \leq 10^9$$$, $$$0 \leq b_i < d_i \leq 10^9$$$) - 的坐标$$$i$$$-th 城堡,其中 $$$(a_i, b_i)$$$ 是左下角的坐标,$$$(c_i, d_i)$$$ 是右上角的坐标。

可以保证没有两座城堡相交,但是它们可能会接触。

输出

如果存在满足故事的可能的一组领土,则打印“YES”,否则打印“NO”。

您可以以任何大小写(大写或小写)打印每个字母。

示例

输入 #1

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

输出 #1

YES

输入 #2

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

输出 #2

NO

注意

第一个和第二个示例中的城堡如下图所示。