/ 
Time Limit: 2.5 sec / Memory Limit: 1024 MiB
配点 : 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