QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#68839#5112. Where Am I?chenshi#AC ✓686ms1581344kbC++141.7kb2022-12-21 10:47:312022-12-21 10:47:32

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-21 10:47:32]
  • 评测
  • 测评结果:AC
  • 用时:686ms
  • 内存:1581344kb
  • [2022-12-21 10:47:31]
  • 提交

answer

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int o=1e6;
int n,m,dx[o],dy[o],cnt,ans1,ans2;char s[110][110];
struct State{int sx,sy,x,y;};
vector<State> bg1,bg2,Ans;
void slv(vector<State> vec,int t){
	if((int)vec.size()==1){
		ans1+=--t;
		if(t>ans2) ans2=t,Ans.clear();
		if(t==ans2) Ans.push_back(vec[0]);
		return;
	}
	for(int c1,c2;1;++t){
		c1=c2=0;
		for(int i=vec.size();i--;){
			vec[i].x+=dx[t];vec[i].y+=dy[t];
			if(vec[i].x>=1&&vec[i].x<=n&&vec[i].y>=1&&vec[i].y<=m&&s[vec[i].x][vec[i].y]=='X') ++c1;
			else ++c2;
		}
		if(c1&&c2){
			vector<State> v1,v2;
			v1.reserve(c1);v2.reserve(c2);
			for(int i=vec.size();i--;)
				if(vec[i].x>=1&&vec[i].x<=n&&vec[i].y>=1&&vec[i].y<=m&&s[vec[i].x][vec[i].y]=='X') v1.push_back(vec[i]);
				else v2.push_back(vec[i]);
			vec.clear();slv(v1,t+1);slv(v2,t+1);
			break;
		}
	}
}
inline bool cmp(State A,State B){if(A.sy^B.sy) return A.sy<B.sy;return A.sx<B.sx;}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<500;++i){
		for(int j=1;j<2*i;++j) dx[++cnt]=0,dy[cnt]=1;
		for(int j=1;j<2*i;++j) dx[++cnt]=1,dy[cnt]=0;
		for(int j=1;j<=2*i;++j) dx[++cnt]=0,dy[cnt]=-1;
		for(int j=1;j<=2*i;++j) dx[++cnt]=-1,dy[cnt]=0;
	}
	for(int j=1;j<=m;++j) for(int i=1;i<=n;++i)
		do s[i][m-j+1]=getchar();while(s[i][m-j+1]-'X'&&s[i][m-j+1]-'.');
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)
		if(s[i][j]=='X') bg1.push_back((State){i,j,i,j});
		else bg2.push_back((State){i,j,i,j});
	if(!bg1.empty()) slv(bg1,1);
	if(!bg2.empty()) slv(bg2,1);
	printf("%.5lf\n%d\n",ans1*1.0/(n*m),ans2);
	sort(Ans.begin(),Ans.end(),cmp);
	for(int i=0,sz=Ans.size();i<sz;++i) printf("(%d,%d) ",Ans[i].sx,Ans[i].sy);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 10808kb

input:

1 1
X

output:

0.00000
0
(1,1) 

result:

ok correct!

Test #2:

score: 0
Accepted
time: 4ms
memory: 10860kb

input:

2 1
.X

output:

0.00000
0
(1,1) (2,1) 

result:

ok correct!

Test #3:

score: 0
Accepted
time: 0ms
memory: 10912kb

input:

2 1
X.

output:

0.00000
0
(1,1) (2,1) 

result:

ok correct!

Test #4:

score: 0
Accepted
time: 5ms
memory: 10848kb

input:

1 2
.
X

output:

0.00000
0
(1,1) (1,2) 

result:

ok correct!

Test #5:

score: 0
Accepted
time: 0ms
memory: 10908kb

input:

1 2
X
.

output:

0.00000
0
(1,1) (1,2) 

result:

ok correct!

Test #6:

score: 0
Accepted
time: 2ms
memory: 10856kb

input:

2 1
XX

output:

3.00000
3
(1,1) (2,1) 

result:

ok correct!

Test #7:

score: 0
Accepted
time: 2ms
memory: 10816kb

input:

3 3
XXX
X.X
XXX

output:

3.11111
5
(3,1) (3,2) 

result:

ok correct!

Test #8:

score: 0
Accepted
time: 120ms
memory: 104808kb

input:

100 100
..X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X..
....................................................................................................
X............................................................................................

output:

4757.94710
9704
(50,1) (50,100) 

result:

ok correct!

Test #9:

score: 0
Accepted
time: 653ms
memory: 1581260kb

input:

100 100
X...................................................................................................
....................................................................................................
.............................................................................................

output:

19735.31990
39599
(100,1) (100,2) 

result:

ok correct!

Test #10:

score: 0
Accepted
time: 654ms
memory: 1581340kb

input:

100 100
....................................................................................................
....................................................................................................
.............................................................................................

output:

19865.66990
39500
(100,1) (100,2) 

result:

ok correct!

Test #11:

score: 0
Accepted
time: 194ms
memory: 31344kb

input:

100 100
X...................................................................................................
.X..................................................................................................
..X..........................................................................................

output:

11855.63920
39302
(100,99) (99,100) 

result:

ok correct!

Test #12:

score: 0
Accepted
time: 195ms
memory: 31328kb

input:

100 100
...................................................................................................X
..................................................................................................X.
.............................................................................................

output:

11854.60980
39104
(1,99) (2,100) 

result:

ok correct!

Test #13:

score: 0
Accepted
time: 0ms
memory: 11676kb

input:

20 73
...........X........
.X..................
....................
X.....X........X....
......X........X....
....................
....................
.X..................
....................
...........X........
.X..................
X...................
.......X........X...
.X....X........X....
...

output:

50.09795
80
(7,6) (16,6) (20,12) (7,15) (16,15) (7,24) (16,24) (7,33) (16,33) (7,42) (16,42) (19,46) (12,47) (20,47) (7,51) (16,51) (12,56) (19,56) (7,60) (16,60) (20,65) (20,67) (7,69) (16,69) 

result:

ok correct!

Test #14:

score: 0
Accepted
time: 5ms
memory: 16632kb

input:

65 57
..............X..................................................
.................................................................
.........................................................X.......
........X.........X..............................................
..X.....X........................

output:

100.71120
742
(1,1) (2,1) 

result:

ok correct!

Test #15:

score: 0
Accepted
time: 10ms
memory: 39140kb

input:

56 59
........................................................
........................................................
........................................................
........................................................
........................................................
X...........

output:

494.49788
1503
(56,38) (56,39) 

result:

ok correct!

Test #16:

score: 0
Accepted
time: 6ms
memory: 17368kb

input:

46 83
..........X...X.................X.............
..............................X...............
...X..........................................
.....................................X........
...X...........................X...X..........
.X............................................
...............

output:

122.54531
387
(1,19) (19,32) 

result:

ok correct!

Test #17:

score: 0
Accepted
time: 2ms
memory: 15160kb

input:

51 57
........................X..........................
............................X......................
....................X.............X................
..................................................X
...................................................
.........................X...........

output:

103.48744
334
(10,57) (11,57) 

result:

ok correct!

Test #18:

score: 0
Accepted
time: 13ms
memory: 47056kb

input:

64 91
................................................................
................................................................
................................................................
................................................................
.....................................

output:

480.57297
1215
(64,71) (63,91) 

result:

ok correct!

Test #19:

score: 0
Accepted
time: 10ms
memory: 14144kb

input:

75 40
.............................................X............X................
....................X..............................X.......................
...........................................X...........X...........X.......
...........................................X.....X......X............

output:

79.14933
319
(1,39) (1,40) 

result:

ok correct!

Test #20:

score: 0
Accepted
time: 5ms
memory: 23640kb

input:

97 54
.............X...................................................................................
..................................X..............................................................
....X............................................................................................
...

output:

383.80832
1084
(93,9) (51,51) 

result:

ok correct!

Test #21:

score: 0
Accepted
time: 0ms
memory: 19620kb

input:

89 49
...............X...........X.............................................................
.............................................................X..X...........X............
.................................X.......................................................
...........................

output:

161.07017
520
(89,1) (2,41) 

result:

ok correct!

Test #22:

score: 0
Accepted
time: 9ms
memory: 21700kb

input:

80 55
.............................................................X..................
................................................................................
.................................................................XX.............
..............................................X.......

output:

176.08318
611
(80,2) (79,37) 

result:

ok correct!

Test #23:

score: 0
Accepted
time: 7ms
memory: 24648kb

input:

61 59
...........X.................................................
.............................................................
.......................................................X.....
.............................................................
...............................X.................

output:

291.70603
860
(1,1) (1,50) 

result:

ok correct!

Test #24:

score: 0
Accepted
time: 6ms
memory: 17392kb

input:

48 74
....X.X.X.......................................
...............X.....X...X......................
..........................................X.....
................................................
................................................
.......X........................................
...

output:

152.16188
512
(48,9) (48,67) 

result:

ok correct!

Test #25:

score: 0
Accepted
time: 10ms
memory: 40020kb

input:

100 96
.................................................................X..................................
.............................X......................................................................
..............................................................................................

output:

212.39625
1031
(1,67) (1,68) 

result:

ok correct!

Test #26:

score: 0
Accepted
time: 23ms
memory: 54880kb

input:

94 84
..............................................................................................
..............................................................................................
..............................................................................................
............

output:

357.12133
2687
(1,83) (1,84) 

result:

ok correct!

Test #27:

score: 0
Accepted
time: 13ms
memory: 33072kb

input:

86 80
...........................................................X..........X...............
......................................................................................
X.....................................................................................
....................................

output:

225.85552
975
(84,1) (85,1) 

result:

ok correct!

Test #28:

score: 0
Accepted
time: 7ms
memory: 19496kb

input:

81 57
.X............X..................................................................
.................................................................................
.....................................X.........X.............X...................
...................................................

output:

139.73403
647
(24,1) (81,4) 

result:

ok correct!

Test #29:

score: 0
Accepted
time: 12ms
memory: 25932kb

input:

65 85
.................................................................
.................................................................
.................................................................
...................X.............................................
.................................

output:

738.97448
3378
(5,45) (5,56) 

result:

ok correct!

Test #30:

score: 0
Accepted
time: 80ms
memory: 224376kb

input:

76 98
............................................................................
............................................................................
............................................................................
..................................................................

output:

1550.39098
4192
(76,34) (76,96) 

result:

ok correct!

Test #31:

score: 0
Accepted
time: 17ms
memory: 46588kb

input:

62 67
..............................................................
..............................................................
.........................X....................................
...................................................X..........
.............................................

output:

648.65022
2420
(16,1) (1,13) 

result:

ok correct!

Test #32:

score: 0
Accepted
time: 1ms
memory: 23124kb

input:

50 98
..........................................X.......
.................................X...............X
..................................................
..................................................
.............................................X....
..........................................

output:

207.33776
895
(1,97) (1,98) 

result:

ok correct!

Test #33:

score: 0
Accepted
time: 13ms
memory: 28196kb

input:

74 97
....................X.....................................................
..........................................................................
..........................................................................
................................X.......................................

output:

193.03023
1078
(74,70) (71,93) 

result:

ok correct!

Test #34:

score: 0
Accepted
time: 46ms
memory: 104664kb

input:

62 77
..............................................................
..............................................................
..............................................................
..............................................................
.............................................

output:

2021.06996
4937
(46,73) (8,77) 

result:

ok correct!

Test #35:

score: 0
Accepted
time: 9ms
memory: 18652kb

input:

47 74
...............................................
...............................................
...............................................
.....................X.........................
...............................................
............................................X..
.........

output:

142.15382
673
(1,74) (2,74) 

result:

ok correct!

Test #36:

score: 0
Accepted
time: 3ms
memory: 16012kb

input:

47 71
...........X....X..............................
...............................................
...............................................
...........X...................................
.............................................X.
..X...........XX............X..................
.........

output:

102.81420
334
(44,4) (47,37) 

result:

ok correct!

Test #37:

score: 0
Accepted
time: 5ms
memory: 14756kb

input:

51 65
.........X..........X..............................
.................................X....X.........X..
................................................X..
...................................................
...................................................
.....................................

output:

81.66998
314
(1,64) (1,65) 

result:

ok correct!

Test #38:

score: 0
Accepted
time: 16ms
memory: 29500kb

input:

40 93
.......X................................
........................................
........................................
........................................
.X......................................
..................X.....................
........................................
..........

output:

300.30753
1326
(39,93) (40,93) 

result:

ok correct!

Test #39:

score: 0
Accepted
time: 21ms
memory: 78368kb

input:

87 99
.......................................................................................
.......................................................................................
.......................................................................................
.................................

output:

474.06897
2063
(1,1) (49,1) 

result:

ok correct!

Test #40:

score: 0
Accepted
time: 23ms
memory: 117244kb

input:

46 94
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
...............

output:

2555.36748
5914
(46,1) (46,2) 

result:

ok correct!

Test #41:

score: 0
Accepted
time: 54ms
memory: 215588kb

input:

93 60
.............................................................................................
.............................................................................................
.............................................................................................
...............

output:

2389.20036
11288
(21,60) (22,60) 

result:

ok correct!

Test #42:

score: 0
Accepted
time: 15ms
memory: 31832kb

input:

98 61
.............................................X................................X...................
...................................................................X.............X................
..................................................................................X................

output:

225.08916
803
(10,61) (11,61) 

result:

ok correct!

Test #43:

score: 0
Accepted
time: 35ms
memory: 40896kb

input:

94 95
..............................................................................................
.......................................................X......................................
............X................................................X.......................X........
............

output:

213.68757
941
(33,89) (33,90) 

result:

ok correct!

Test #44:

score: 0
Accepted
time: 26ms
memory: 32768kb

input:

94 72
..............................................................................................
..............................................................................................
..............................................................................................
............

output:

1330.08954
4671
(60,71) (38,72) 

result:

ok correct!

Test #45:

score: 0
Accepted
time: 7ms
memory: 12788kb

input:

46 44
....X...X..............................X...X..
................................X..X......X...
..............X.........X.....................
......................X...........X...........
......................X.X........X.X...X......
.............X..........X.....................
.X.............

output:

67.35474
645
(1,1) (2,1) 

result:

ok correct!

Test #46:

score: 0
Accepted
time: 2ms
memory: 14852kb

input:

65 51
.................................................................
.........................X.......................................
........X..............X.........................................
....X...............X............................................
.................................

output:

80.04103
332
(64,34) (65,34) 

result:

ok correct!

Test #47:

score: 0
Accepted
time: 3ms
memory: 17048kb

input:

51 82
...................................................
...............X...........X.........X.............
..............................X....................
...................................................
...................................................
.......................X.............

output:

100.46604
360
(49,3) (51,62) 

result:

ok correct!

Test #48:

score: 0
Accepted
time: 4ms
memory: 29908kb

input:

87 60
.......................................................................................
........................................................................X..............
.......................................................................................
.................................

output:

302.78985
799
(87,29) (87,58) 

result:

ok correct!

Test #49:

score: 0
Accepted
time: 2ms
memory: 15828kb

input:

53 44
...................................X.................
.....................................................
............................X....X...................
...X.................................................
.....................................................
....................X......

output:

150.34691
930
(52,44) (53,44) 

result:

ok correct!

Test #50:

score: 0
Accepted
time: 29ms
memory: 91900kb

input:

94 97
..............................................................................................
.......................................X......................X...............................
..............................................................................................
............

output:

690.64641
3826
(1,96) (1,97) 

result:

ok correct!

Test #51:

score: 0
Accepted
time: 9ms
memory: 23428kb

input:

70 68
......................................................................
.....................X...........................X....................
........X...........................X...........................X.....
......................................................................
.............

output:

356.97458
1620
(23,68) (51,68) 

result:

ok correct!

Test #52:

score: 0
Accepted
time: 71ms
memory: 158356kb

input:

100 91
....................................................................................................
....................................................................................................
..............................................................................................

output:

1705.10220
4664
(100,44) (100,90) 

result:

ok correct!

Test #53:

score: 0
Accepted
time: 109ms
memory: 338520kb

input:

88 84
........................................................................................
........................................................................................
........................................................................................
..............................

output:

2976.14232
8305
(68,1) (69,1) 

result:

ok correct!

Test #54:

score: 0
Accepted
time: 2ms
memory: 15148kb

input:

48 44
................................................
................................................
..........X...........X.........................
...X............................................
...........................X....................
.........X......................................
...

output:

140.18797
466
(8,7) (1,20) 

result:

ok correct!

Test #55:

score: 0
Accepted
time: 2ms
memory: 22240kb

input:

98 60
......................................X.....X.....................................................
......................................X..............................X............................
............X......................................................X...............................

output:

179.27925
713
(98,56) (98,57) 

result:

ok correct!

Test #56:

score: 0
Accepted
time: 9ms
memory: 13344kb

input:

58 41
...............................X...............X..........
..X..................X....X...............................
..........................................................
.....................X.............................X......
..............................X.................X............

output:

75.12952
228
(2,1) (49,27) 

result:

ok correct!

Test #57:

score: 0
Accepted
time: 4ms
memory: 17044kb

input:

95 48
....X.......X.......................X..............X........................X...........X......
........X...............................X...............................X......................
........................XX...............................X.....................................
.........

output:

115.94057
390
(15,48) (79,48) 

result:

ok correct!

Test #58:

score: 0
Accepted
time: 5ms
memory: 15828kb

input:

51 62
...................................................
..............................X.........X..........
................................................X..
.......................X...........................
..............................................X....
.....................................

output:

127.05028
432
(7,1) (51,6) 

result:

ok correct!

Test #59:

score: 0
Accepted
time: 19ms
memory: 37820kb

input:

86 98
.......X......X.......................................................................
......................................................................................
......................................................................................
....................................

output:

215.50095
732
(66,70) (68,72) 

result:

ok correct!

Test #60:

score: 0
Accepted
time: 17ms
memory: 51444kb

input:

91 94
...........................................................................................
...........................................................................................
...........................................................................................
.....................

output:

309.11036
1541
(78,1) (90,8) 

result:

ok correct!

Test #61:

score: 0
Accepted
time: 9ms
memory: 19288kb

input:

74 45
..........................................................................
..........................................................................
....X.............X..........................................X............
.X................X..........................X............X.............

output:

164.87808
772
(1,7) (1,8) 

result:

ok correct!

Test #62:

score: 0
Accepted
time: 4ms
memory: 16464kb

input:

54 73
.....X.......X........................................
.............X........................................
...............X......................................
................................X.....................
..............................................X.......
......................

output:

106.01294
560
(1,1) (1,2) 

result:

ok correct!

Test #63:

score: 0
Accepted
time: 6ms
memory: 18660kb

input:

91 56
...........................................................................................
..............................X.............................X..............................
.....................................................................X.....................
.....................

output:

423.71487
1455
(63,19) (24,20) 

result:

ok correct!

Test #64:

score: 0
Accepted
time: 4ms
memory: 10860kb

input:

1 2
X
X

output:

1.00000
1
(1,1) (1,2) 

result:

ok correct!

Test #65:

score: 0
Accepted
time: 1ms
memory: 10888kb

input:

1 3
X
.
.

output:

0.66667
1
(1,1) (1,2) 

result:

ok correct!

Test #66:

score: 0
Accepted
time: 4ms
memory: 10868kb

input:

1 3
.
X
.

output:

0.66667
1
(1,1) (1,3) 

result:

ok correct!

Test #67:

score: 0
Accepted
time: 2ms
memory: 10708kb

input:

1 3
X
X
.

output:

0.66667
1
(1,2) (1,3) 

result:

ok correct!

Test #68:

score: 0
Accepted
time: 2ms
memory: 10908kb

input:

1 3
.
.
X

output:

3.33333
5
(1,2) (1,3) 

result:

ok correct!

Test #69:

score: 0
Accepted
time: 2ms
memory: 10884kb

input:

1 3
X
.
X

output:

6.66667
10
(1,1) (1,3) 

result:

ok correct!

Test #70:

score: 0
Accepted
time: 4ms
memory: 10760kb

input:

1 3
.
X
X

output:

0.66667
1
(1,1) (1,2) 

result:

ok correct!

Test #71:

score: 0
Accepted
time: 4ms
memory: 10748kb

input:

1 3
X
X
X

output:

3.66667
5
(1,1) (1,2) 

result:

ok correct!

Test #72:

score: 0
Accepted
time: 2ms
memory: 10960kb

input:

1 4
X
.
.
.

output:

5.25000
10
(1,1) (1,2) 

result:

ok correct!

Test #73:

score: 0
Accepted
time: 4ms
memory: 10812kb

input:

1 4
.
X
.
.

output:

2.75000
5
(1,1) (1,4) 

result:

ok correct!

Test #74:

score: 0
Accepted
time: 0ms
memory: 10800kb

input:

1 4
X
X
.
.

output:

1.00000
1
(1,1) (1,2) (1,3) (1,4) 

result:

ok correct!

Test #75:

score: 0
Accepted
time: 2ms
memory: 10852kb

input:

1 4
.
.
X
.

output:

2.75000
5
(1,3) (1,4) 

result:

ok correct!

Test #76:

score: 0
Accepted
time: 1ms
memory: 10888kb

input:

1 4
X
.
X
.

output:

7.50000
10
(1,2) (1,4) 

result:

ok correct!

Test #77:

score: 0
Accepted
time: 0ms
memory: 10912kb

input:

1 4
.
X
X
.

output:

1.00000
1
(1,1) (1,2) (1,3) (1,4) 

result:

ok correct!

Test #78:

score: 0
Accepted
time: 5ms
memory: 10848kb

input:

1 4
X
X
X
.

output:

2.75000
5
(1,2) (1,3) 

result:

ok correct!

Test #79:

score: 0
Accepted
time: 2ms
memory: 10804kb

input:

1 4
.
.
.
X

output:

10.25000
18
(1,3) (1,4) 

result:

ok correct!

Test #80:

score: 0
Accepted
time: 2ms
memory: 10976kb

input:

1 4
X
.
.
X

output:

14.00000
27
(1,1) (1,4) 

result:

ok correct!

Test #81:

score: 0
Accepted
time: 5ms
memory: 10956kb

input:

1 4
.
X
.
X

output:

5.50000
10
(1,1) (1,3) 

result:

ok correct!

Test #82:

score: 0
Accepted
time: 5ms
memory: 10952kb

input:

1 4
X
X
.
X

output:

2.75000
5
(1,1) (1,4) 

result:

ok correct!

Test #83:

score: 0
Accepted
time: 2ms
memory: 10864kb

input:

1 4
.
.
X
X

output:

3.00000
5
(1,3) (1,4) 

result:

ok correct!

Test #84:

score: 0
Accepted
time: 1ms
memory: 10804kb

input:

1 4
X
.
X
X

output:

2.75000
5
(1,2) (1,4) 

result:

ok correct!

Test #85:

score: 0
Accepted
time: 2ms
memory: 10828kb

input:

1 4
.
X
X
X

output:

2.75000
5
(1,1) (1,2) 

result:

ok correct!

Test #86:

score: 0
Accepted
time: 4ms
memory: 10816kb

input:

1 4
X
X
X
X

output:

6.50000
10
(1,2) (1,3) 

result:

ok correct!

Test #87:

score: 0
Accepted
time: 2ms
memory: 10956kb

input:

2 2
X.
..

output:

3.75000
7
(2,1) (2,2) 

result:

ok correct!

Test #88:

score: 0
Accepted
time: 2ms
memory: 10744kb

input:

2 2
.X
..

output:

1.25000
2
(1,1) (1,2) 

result:

ok correct!

Test #89:

score: 0
Accepted
time: 4ms
memory: 10888kb

input:

2 2
XX
..

output:

2.50000
3
(1,2) (2,2) 

result:

ok correct!

Test #90:

score: 0
Accepted
time: 2ms
memory: 10956kb

input:

2 2
..
X.

output:

4.25000
6
(2,1) (2,2) 

result:

ok correct!

Test #91:

score: 0
Accepted
time: 0ms
memory: 10864kb

input:

2 2
X.
X.

output:

3.50000
6
(2,1) (2,2) 

result:

ok correct!

Test #92:

score: 0
Accepted
time: 2ms
memory: 10868kb

input:

2 2
.X
X.

output:

1.50000
2
(1,1) (2,2) 

result:

ok correct!

Test #93:

score: 0
Accepted
time: 2ms
memory: 10852kb

input:

2 2
XX
X.

output:

1.75000
3
(1,2) (2,2) 

result:

ok correct!

Test #94:

score: 0
Accepted
time: 4ms
memory: 10796kb

input:

2 2
..
.X

output:

2.75000
4
(1,2) (2,2) 

result:

ok correct!

Test #95:

score: 0
Accepted
time: 0ms
memory: 10940kb

input:

2 2
X.
.X

output:

2.50000
4
(2,1) (1,2) 

result:

ok correct!

Test #96:

score: 0
Accepted
time: 2ms
memory: 10756kb

input:

2 2
.X
.X

output:

1.50000
2
(1,1) (1,2) 

result:

ok correct!

Test #97:

score: 0
Accepted
time: 1ms
memory: 10868kb

input:

2 2
XX
.X

output:

1.75000
3
(1,2) (2,2) 

result:

ok correct!

Test #98:

score: 0
Accepted
time: 4ms
memory: 10816kb

input:

2 2
..
XX

output:

3.50000
4
(1,2) (2,2) 

result:

ok correct!

Test #99:

score: 0
Accepted
time: 2ms
memory: 10960kb

input:

2 2
X.
XX

output:

2.25000
4
(2,1) (1,2) 

result:

ok correct!

Test #100:

score: 0
Accepted
time: 2ms
memory: 10892kb

input:

2 2
.X
XX

output:

1.25000
2
(1,1) (2,2) 

result:

ok correct!

Test #101:

score: 0
Accepted
time: 4ms
memory: 10868kb

input:

2 2
XX
XX

output:

2.50000
3
(1,2) (2,2) 

result:

ok correct!

Test #102:

score: 0
Accepted
time: 1ms
memory: 10788kb

input:

3 1
X..

output:

4.66667
7
(2,1) (3,1) 

result:

ok correct!

Test #103:

score: 0
Accepted
time: 2ms
memory: 10796kb

input:

3 1
.X.

output:

2.00000
3
(1,1) (3,1) 

result:

ok correct!

Test #104:

score: 0
Accepted
time: 2ms
memory: 10744kb

input:

3 1
XX.

output:

2.00000
3
(1,1) (2,1) 

result:

ok correct!

Test #105:

score: 0
Accepted
time: 1ms
memory: 10908kb

input:

3 1
..X

output:

2.00000
3
(1,1) (2,1) 

result:

ok correct!

Test #106:

score: 0
Accepted
time: 2ms
memory: 10868kb

input:

3 1
X.X

output:

9.33333
14
(1,1) (3,1) 

result:

ok correct!

Test #107:

score: 0
Accepted
time: 0ms
memory: 10848kb

input:

3 1
.XX

output:

2.00000
3
(2,1) (3,1) 

result:

ok correct!

Test #108:

score: 0
Accepted
time: 4ms
memory: 10852kb

input:

3 1
XXX

output:

5.66667
7
(1,1) (2,1) 

result:

ok correct!

Test #109:

score: 0
Accepted
time: 2ms
memory: 10864kb

input:

4 1
X...

output:

12.75000
22
(3,1) (4,1) 

result:

ok correct!

Test #110:

score: 0
Accepted
time: 1ms
memory: 10852kb

input:

4 1
.X..

output:

4.25000
7
(3,1) (4,1) 

result:

ok correct!

Test #111:

score: 0
Accepted
time: 0ms
memory: 10808kb

input:

4 1
XX..

output:

5.00000
7
(3,1) (4,1) 

result:

ok correct!

Test #112:

score: 0
Accepted
time: 2ms
memory: 10868kb

input:

4 1
..X.

output:

4.25000
7
(1,1) (4,1) 

result:

ok correct!

Test #113:

score: 0
Accepted
time: 4ms
memory: 10952kb

input:

4 1
X.X.

output:

8.50000
14
(1,1) (3,1) 

result:

ok correct!

Test #114:

score: 0
Accepted
time: 5ms
memory: 10968kb

input:

4 1
.XX.

output:

3.00000
3
(1,1) (2,1) (3,1) (4,1) 

result:

ok correct!

Test #115:

score: 0
Accepted
time: 4ms
memory: 10952kb

input:

4 1
XXX.

output:

4.25000
7
(1,1) (2,1) 

result:

ok correct!

Test #116:

score: 0
Accepted
time: 0ms
memory: 10800kb

input:

4 1
...X

output:

7.75000
14
(1,1) (2,1) 

result:

ok correct!

Test #117:

score: 0
Accepted
time: 0ms
memory: 10912kb

input:

4 1
X..X

output:

18.00000
33
(1,1) (4,1) 

result:

ok correct!

Test #118:

score: 0
Accepted
time: 3ms
memory: 10912kb

input:

4 1
.X.X

output:

10.50000
14
(2,1) (4,1) 

result:

ok correct!

Test #119:

score: 0
Accepted
time: 2ms
memory: 10864kb

input:

4 1
XX.X

output:

4.25000
7
(2,1) (4,1) 

result:

ok correct!

Test #120:

score: 0
Accepted
time: 1ms
memory: 10852kb

input:

4 1
..XX

output:

3.00000
3
(1,1) (2,1) (3,1) (4,1) 

result:

ok correct!

Test #121:

score: 0
Accepted
time: 4ms
memory: 10796kb

input:

4 1
X.XX

output:

4.25000
7
(1,1) (4,1) 

result:

ok correct!

Test #122:

score: 0
Accepted
time: 2ms
memory: 10948kb

input:

4 1
.XXX

output:

4.25000
7
(2,1) (3,1) 

result:

ok correct!

Test #123:

score: 0
Accepted
time: 0ms
memory: 10808kb

input:

4 1
XXXX

output:

9.50000
14
(2,1) (3,1) 

result:

ok correct!

Test #124:

score: 0
Accepted
time: 6ms
memory: 11132kb

input:

100 1
X...................................................................................................

output:

13274.59000
38710
(99,1) (100,1) 

result:

ok correct!

Test #125:

score: 0
Accepted
time: 0ms
memory: 10972kb

input:

100 1
...................................................................................................X

output:

13076.63000
38318
(1,1) (2,1) 

result:

ok correct!

Test #126:

score: 0
Accepted
time: 2ms
memory: 11144kb

input:

100 1
..................................................X.................................................

output:

3356.01000
9751
(1,1) (100,1) 

result:

ok correct!

Test #127:

score: 0
Accepted
time: 4ms
memory: 11028kb

input:

100 1
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

output:

3457.50000
9950
(50,1) (51,1) 

result:

ok correct!

Test #128:

score: 0
Accepted
time: 5ms
memory: 10876kb

input:

100 1
X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.

output:

3554.94000
9950
(49,1) (51,1) 

result:

ok correct!

Test #129:

score: 0
Accepted
time: 0ms
memory: 10924kb

input:

100 2
X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.
.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X

output:

3451.07000
9751
(49,1) (51,1) 

result:

ok correct!

Test #130:

score: 0
Accepted
time: 2ms
memory: 11020kb

input:

1 100
X
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

output:

12977.65000
38122
(1,1) (1,2) 

result:

ok correct!

Test #131:

score: 0
Accepted
time: 6ms
memory: 10912kb

input:

1 100
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
X

output:

13175.61000
38514
(1,99) (1,100) 

result:

ok correct!

Test #132:

score: 0
Accepted
time: 5ms
memory: 11020kb

input:

1 100
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
X
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

output:

3306.03000
9653
(1,99) (1,100) 

result:

ok correct!

Test #133:

score: 0
Accepted
time: 2ms
memory: 11084kb

input:

1 100
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X

output:

3406.50000
9850
(1,50) (1,51) 

result:

ok correct!

Test #134:

score: 0
Accepted
time: 4ms
memory: 11000kb

input:

1 100
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.

output:

3503.02000
9850
(1,50) (1,52) 

result:

ok correct!

Test #135:

score: 0
Accepted
time: 0ms
memory: 10800kb

input:

2 100
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
...

output:

3401.11000
9654
(2,49) (2,51) 

result:

ok correct!

Test #136:

score: 0
Accepted
time: 4ms
memory: 10836kb

input:

10 10
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX

output:

58.08000
95
(5,10) (6,10) 

result:

ok correct!

Test #137:

score: 0
Accepted
time: 346ms
memory: 522780kb

input:

100 100
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
....................................................................................................
.............................................................................................

output:

13878.92750
38908
(99,1) (100,1) 

result:

ok correct!

Test #138:

score: 0
Accepted
time: 298ms
memory: 538292kb

input:

100 100
....................................................................................................
....................................................................................................
.............................................................................................

output:

14059.27250
39302
(99,100) (100,100) 

result:

ok correct!

Test #139:

score: 0
Accepted
time: 362ms
memory: 538260kb

input:

100 100
X...................................................................................................
X...................................................................................................
X............................................................................................

output:

14132.28250
39500
(100,1) (100,2) 

result:

ok correct!

Test #140:

score: 0
Accepted
time: 332ms
memory: 538268kb

input:

100 100
...................................................................................................X
...................................................................................................X
.............................................................................................

output:

13951.43250
39104
(1,99) (1,100) 

result:

ok correct!

Test #141:

score: 0
Accepted
time: 686ms
memory: 1581340kb

input:

100 100
....................................................................................................
....................................................................................................
.............................................................................................

output:

19733.33990
39302
(99,100) (100,100) 

result:

ok correct!

Test #142:

score: 0
Accepted
time: 593ms
memory: 1581340kb

input:

100 100
...................................................................................................X
....................................................................................................
.............................................................................................

output:

19601.00990
39104
(1,99) (1,100) 

result:

ok correct!

Test #143:

score: 0
Accepted
time: 539ms
memory: 1581344kb

input:

100 100
....................................................................................................
....................................................................................................
.............................................................................................

output:

5001.48990
10098
(99,100) (100,100) 

result:

ok correct!

Test #144:

score: 0
Accepted
time: 0ms
memory: 10864kb

input:

20 20
.XX......XX.....XXXX
..X.....X..X....X...
.....X..............
X..XX.X..XX......XX.
X..........X........
...X..X............X
.X...X..........XXXX
.X...XX..XX....X....
X.X.XX...X.......X.X
XXXXX....X........X.
.X.XX.X..XX...X.X...
X.......X..XXX.....X
.X..X..X.X......X...
.........X....X...X.
...

output:

12.81250
31
(13,5) (15,18) 

result:

ok correct!

Test #145:

score: 0
Accepted
time: 1ms
memory: 12744kb

input:

50 50
..................................................
..................X...............X...............
..................................................
....X...X........................X........X..X....
.................X................................
..........................................

output:

60.83080
195
(28,1) (1,35) 

result:

ok correct!

Test #146:

score: 0
Accepted
time: 19ms
memory: 42768kb

input:

100 100
....................................................................................................
....................................................................................................
.............................................................................................

output:

227.53490
1062
(96,95) (55,100) 

result:

ok correct!

Extra Test:

score: 0
Extra Test Passed