← 返回题目列表

AtCoder · kupc2024_c

C. 切蛋糕仪式

中文机器翻译题面 查看原题

配点 : 100 点

問題文

今天,双胞胎 K 和你在一起 U 今天是你的生日。

2 对于人们来说,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} = . 当该区域被奶油覆盖时。

现在让我们开始做这个蛋糕吧。 切成 2 块,每块 K 和你在一起 U 我需要把它给你。2 每个人都喜欢巧克力奶油和草莓奶油,所以2 如果蛋糕中巧克力奶油和草莓奶油的面积两侧不同,则将不满意(奶油的面积无关紧要)。

你的工作是做蛋糕 1 沿着书本的直线切割,2 这是为了让人们满意。如果存在这样的切割方法,则需要切割的直线和蛋糕的轮廓。 请输出 2 交点的坐标,如果不存在,请输出该事实。

制約

  • N 是 您也可以写 1 \le N \le 2025 的整数 选择
  • c_{i,j} 是 您也可以写 c、s、. 任何一个
  • c_{i,j} = c 或 至少 c_{i,j} = s 实现 (i,j) 至少 1 设置存在

部分点

如果您对满足以下约束的数据集回答正确: 1 点。 如果您正确回答了所有满足

  • N 是 您也可以写 1 \le N \le 105 的整数 选择
  • c_{i,j} 是 您也可以写 c、s 任何一个


入力

输入是按以下格式从标准输入给出的。

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}

出力

2 如果有一种让人满意的切割方法,要切割的直线和蛋糕的轮廓应该是 2 交点坐标 (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

3
scs
..c
.sc

出力例 1

Yes
0.23670068 0.00000000
1.81649658 3.00000000

入力例 2

2
sc
cs

出力例 2

Yes
0.00000000 2.00000000
2.00000000 0.00000000

入力例 3

11
.c..c.s..s.
.c.c..s..s.
.cc...s..s.
.c.c..s..s.
.c..c..ss..
...........
.sss...ccc.
.s..s.c....
.sss..c....
.s....c....
.s.....ccc.

出力例 3

Yes
11.00000000 10.60555128
0.39444872 0.00000000