logo AlgoBeat OnlineJudge
登录 注册

#215303. [NWERC 2025] Illuminated Stalls

内存限制:2048 MiB 时间限制:8000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

年复一年,你漫步在圣诞市场,一边喝着热红酒一边与老朋友叙旧。
最近价格已经变得荒谬,仅仅几个晚上就让你陷入财务困境。
今年,你决定扭转局面,开一个卖热红酒的摊位。
但竞争很激烈,结果又一个价格高得离谱的摊位远不如你希望的那么有利可图。

为了脱颖而出,你设计了一个难题。
如果顾客解开了它,他们就可以免费喝到他们想要的任意多的热红酒。
天真的顾客通常愿意支付比平常更多的钱。

这个谜题由挂在墙上的 个直线形状的霓虹灯管组成。
它们的朝向要么是水平的,要么是垂直的。
没有两个水平灯管重叠或接触,也没有两个垂直灯管重叠或接触,但垂直灯管可以与水平灯管相交或接触。
玩家最多可以按照他们喜欢的任何方式旋转和/或移动一个灯管。
目标是至少有一个发光的霓虹灯正方形。
这个正方形的四条边必须完全被霓虹灯覆盖,但灯的长度可以比正方形的边长长。

灯管允许位于正方形的内部或与其边相交。
被移动的灯管可以放置成与其他共线的灯管接触、部分重叠或完全重叠。

你想让这个谜题尽可能难,但如果没有有效的解决方案,你将遇到德国立法者的麻烦,因为法规非常严格。
给定一个谜题,找出是否有一种方法,通过移动和/或旋转最多一个灯管来构成一个正方形。

输入格式

输入包括:

  • 一行一个整数 (),表示测试用例的数量。
  • 对于每个测试用例,输入包括:
    • 一行一个整数 (),表示霓虹灯管的数量。
    • 行,每行四个整数 (,且要么 ,要么 ,但不同时满足),其中 是一个灯管的端点。
      所有测试用例的灯管总数不超过

所有灯管要么是垂直的,要么是水平的。
对于每个测试用例,初始配置中没有两个水平灯管重叠或接触,也没有两个垂直灯管重叠或接触。
注意水平灯管可以与垂直灯管相交或接触。

输出格式

对于每个测试用例,如果有一种方法通过移动和/或旋转最多一个灯管来构成一个正方形,则输出 "yes",否则输出 "no"。

样例

样例输入 1

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

样例输出 1

yes
yes
no
yes
yes

数据范围与提示


:左边显示了样例输入 的第五个测试用例的初始灯管配置。右边,紫色的霓虹灯被旋转和移动以构成一个 的正方形。