J. 霓虹灯正方形

Illuminated Stalls

时间限制：8 秒 · 内存限制：1024 MiB

原题：NWERC 2025 I · 查看官方英文原文（英文 PDF 也已作为本题附件提供）

题目描述

墙上装有 $n$ 根霓虹灯管，每根灯管是一条水平或竖直的非零长度线段。初始状态下，任意两根水平灯管既不相交也不接触，任意两根竖直灯管也既不相交也不接触；水平灯管与竖直灯管之间则可以相交或接触。

你最多可以选一根灯管，对它进行任意平移和/或旋转，但不能改变它的长度。其余灯管保持原位。你希望存在一个边长大于 $0$ 的正方形，使其四条边都被灯管完全覆盖；灯管可以比正方形的边更长。

允许有其他灯管位于正方形内部或穿过正方形的边。被移动的灯管允许与其他共线灯管接触、部分重叠或完全重叠。请判断能否达到目标；如果初始状态已有正方形，可以不移动任何灯管。

输入格式

第一行包含测试数量 $t$（$1 \leq t \leq 20000$）。

每组测试先给出 $n$（$4 \leq n \leq 200000$），随后 $n$ 行，每行包含 $x_{1}$、$y_{1}$、$x_{2}$、$y_{2}$，表示一根灯管的两个端点。

坐标均为整数，满足 $0 \leq x_{1}, x_{2}, y_{1}, y_{2} \leq 10^{9}$，$x_{1} \leq x_{2}$，$y_{1} \leq y_{2}$，且 $x_{1} = x_{2}$ 与 $y_{1} = y_{2}$ 中恰好一个成立。

所有测试中的 $n$ 之和不超过 $200000$，且初始布局满足题目给出的同向灯管不相交、不接触条件。

输出格式

每组测试输出一行：如果可以形成正方形，输出 yes，否则输出 no。

样例

5
4
0 0 0 1
0 1 1 1
1 0 1 1
0 0 1 0
4
0 0 0 4
0 4 4 4
4 0 4 4
10 10 10 14
5
0 0 0 4
0 4 4 4
3 1 4 1
4 0 4 4
10 10 10 13
5
0 0 0 4
0 4 4 4
4 0 4 4
3 0 4 0
10 10 10 13
9
1 3 6 3
2 1 2 8
2 7 8 7
4 6 6 6
6 7 6 8
5 5 7 5
6 2 6 4
7 3 11 3
9 1 9 5

yes
yes
no
yes
yes

原题版权归原作者及相应赛事评委会所有，采用 CC BY-SA 4.0 许可。中文译文为本练习赛整理，按相同许可发布。题号及中文标题作了调整，输入约束、样例和判题要求依照官方原题；图示及完整英文叙述请参阅英文原文附件。