P13708 [NWERC 2023] Isolated Island

在一个遥远的小岛上，住着几位与世隔绝的老人。整个小岛被篱笆分割成若干块土地，每位老人拥有一块被篱笆完全包围的土地（所有篱笆外的区域为大海）。每位居民都需要捕鱼为生，而唯一可以捕鱼的地方就是环绕小岛的大海。由于并非每块土地都与大海直接相连，有些老人需要经过他人的土地才能到达大海。老人们每次只能跨越一段篱笆，不能经过篱笆柱或篱笆交点。 不幸的是，这些老人都很贪婪。每当有人想进入他们的土地时，都要交一条鱼。为了尽量少交鱼，每位老人都会选择一条需要交最少鱼的路径到达大海。 多年下来，这导致了老人们之间的矛盾。每位老人都讨厌那些比自己交更少鱼就能到达大海的人。只有当两位老人到达大海所需交的鱼数量相同时，他们才会“喜欢”对方。 现在有一个自然的问题：岛上是否存在一对相邻（即土地仅隔一段篱笆相邻）的老人，他们彼此喜欢？见下图 I.1，展示了前几个样例输入的情况。 |||| |:---:|:---:|:---:| :::align{center} 图 I.1：前三个样例输入的示意图。在样例 1 中，每位老人都能直接到达大海，因此他们都彼此喜欢。在样例 2 中，没有一对相邻的老人彼此喜欢，因为中间的老人需要交一条鱼，而他的邻居们都不需要交鱼。在样例 3 中，有六位老人，其中有些是友好的邻居。 ::: 现在的问题是：岛上是否存在一对相邻且彼此喜欢的老人？

输入包含： - 一行一个整数 $n$（$3 \le n \le 1000$），表示篱笆的数量。 - 接下来 $n$ 行，每行四个整数 $x_1$、$y_1$、$x_2$、$y_2$（$|x_1|, |y_1|, |x_2|, |y_2| \leq 10^6$，$(x_1, y_1) \neq (x_2, y_2)$），表示一段连接 $(x_1, y_1)$ 和 $(x_2, y_2)$ 的直线篱笆。 注意：篱笆可能在内部相交，且三条或更多篱笆可能在同一点相交。 保证任意两段篱笆至多在一个点相交。每次跨越一段篱笆，必然进入一个不同的区域。所有区域共同组成一个连通的岛屿，任意区域都可以通过若干次跨越篱笆到达其它任意区域。

如果存在一对相邻且彼此喜欢的老人，则输出“yes”。否则输出“no”。

由 ChatGPT 4.1 翻译