P7210: 看门狗二

---

【题目描述】

【题目描述】
一家公司在市中心有一栋办公楼。这座建筑有一个完美的方形屋顶，屋顶上有许多舱口。因为一系列入室盗窃案的犯罪者都是从这些舱口进入的，所以该公司决定用一只看门狗来守卫舱口。选择了一种特别恶毒但又相当愚蠢的狗，不幸的是，这只狗在第三次值班时从屋顶上掉了下来。
公司又买一只新狗，并决定在它的项圈上系上一条皮带，另一端系在屋顶的某个地方。然而，如果皮带太短，狗就无法到达所有舱口，但如果皮带太长，狗就会再次从建筑物上掉下来。皮带的两端都有钩子，所以没有任何部分用来打结。该公司希望狗能到达每个舱口的中心（如果狗平躺在屋顶上，狗能到达的距离正好是皮带能到达的距离），但它不希望牵引绳超出屋顶的边缘（可以到边缘）。他们希望，通过仔细选择皮带的长度和连接位置，这只狗将能够到达所有舱口，而不会有从屋顶掉下来的风险。皮带只能连接在具有整数坐标的点上（如果建筑物为10乘10米，则建筑物的西南角具有坐标（0,0），东北角具有坐标为（10,10））。皮带不能系在有舱口的地方。
如果没有地方可以拴上皮带，够到所有舱口，但不能够到屋顶边缘以外，那么就不可能使用这只狗，公司将改用poodle（这是一种不那么凶猛的狗，但也不太容易从建筑物上掉下来）。
【输入】
输入的第一行是一个N≤100的正整数，表示接下来要进行的测试用例的数量。每种情况都从一行开始，行中有两个整数S,H，其中S是偶数，2≤S≤40，1≤H≤50。S是以米为单位的方形屋顶的侧面，H是舱口的数量。以下H线各包含两个整数X和Y。这是舱口的坐标。舱口永远不会位于屋顶外或屋顶周边。没有两个舱口会占据相同的位置。
【输出】
对于每个测试用例，输出一条包含坐标X、Y的线，在该坐标系上皮带（如果有几个可能的点，则输出X最小的一个，如果仍有几个可能性，则在X最小的点中选择Y最小的那一个），这样，长度合适的皮带就可以进入所有舱口，而不会延伸到屋顶边缘之外。如果没有这一点，则为该测试用例输出“poodle”。
【样本输入1】
3
10 2
6 6
5 4
20 2
1 1
19 19
10 3
1 1
1 2
1 3
【样本输出1】
3 6
poodle
2 2

题目类型~

初级 难度2.2 

咻咻~

提交答案 状态 返回