AT_kupc2024_c.Cake-Cutting Ceremony

今天是双胞胎 $K$ 君和 $U$ 君的生日。

为二位准备了一块在 $xy$ 平面上 $0 \le x, y \le N$ 内，用每条边长为 $N$ 的正方形表示的生日蛋糕。

对于满足 $1 \le i,j \le N$ 的整数 $i,j$，$c_{i,j}$ 表示平面上 $i-1 \le x \le i$ 且 $j-1 \le y \le j$ 这个区域所涂抹的奶油种类。

• 当 $c_{i,j} = $ c 时，该区域被涂上的是巧克力奶油。
• 当 $c_{i,j} = $ s 时，该区域被涂上的是草莓奶油。
• 当 $c_{i,j} = $ . 时，该区域被涂上的是黄油奶油。

现在需要将这块蛋糕用一条直线切割成两块，然后分别分给 $K$ 君和 $U$ 君。两位都对巧克力奶油和草莓奶油情有独钟，所以若分成的两块蛋糕中含有的巧克力奶油和草莓奶油的面积有任何一项不同，则他们都不会满意（黄油奶油的面积可以不同，不影响满意度）。

你的任务是，沿着一条直线切割蛋糕，使得两人都满意。如果存在这样的切法，请输出切割该蛋糕的直线与蛋糕边界的两个交点的坐标；如果不存在，请输出相应信息。

输入由标准输入给出，格式如下：

$N$ $c_{1,1}$ $c_{1,2}$ $\cdots$ $c_{1,N}$ $c_{2,1}$ $c_{2,2}$ $\cdots$ $c_{2,N}$ $\vdots$ $c_{N,1}$ $c_{N,2}$ $\cdots$ $c_{N,N}$

如果存在能够让两人都满意的切法，输出要切的直线与蛋糕边界的两个交点的坐标 $(x_1, y_1)$ 和 $(x_2, y_2)$，格式如下。如果不存在，输出 No。

Yes $x_1$ $y_1$ $x_2$ $y_2$

假设按照输出方式切割蛋糕后，将蛋糕的一部分记为 $P$，另一部分记为 $Q$，$P$ 包含的巧克力奶油面积为 $P_c$，草莓奶油面积为 $P_s$，$Q$ 包含的巧克力奶油面积为 $Q_c$，草莓奶油面积为 $Q_s$，则若 $|P_c - Q_c| \le 10^{-3}$ 且 $|P_s - Q_s| \le 10^{-3}$，判定为正确答案。

部分分

对于满足下列限制的数据集，答对给予 $1$ 分：

• $N$ 满足 $1 \le N \le 105$ 的正整数
• $c_{i,j}$ 只会为 c 或 s

限制条件

• $N$ 满足 $1 \le N \le 2025$ 的正整数
• $c_{i,j}$ 为 c、s 或 .的任一种
• 存在至少一组 $(i, j)$ 满足 $c_{i,j} = $ c 或 $c_{i,j} = $ s

由 ChatGPT 5 翻译