QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#357524#5112. Where Am I?TadijaSebezAC ✓528ms8056kbC++141.5kb2024-03-18 22:18:252024-03-18 22:18:26

Judging History

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

  • [2024-03-18 22:18:26]
  • 评测
  • 测评结果:AC
  • 用时:528ms
  • 内存:8056kb
  • [2024-03-18 22:18:25]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define pb push_back

const int N=105;
char s[N][N];
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};

int Get(vector<int> a,vector<int> b){
	int tmp=0;
	while(a[tmp]==b[tmp])tmp++;
	return min(a[tmp],b[tmp]);
}
int main(){
	int n,m;
	scanf("%i %i",&m,&n);
	int xs=0;
	for(int i=1;i<=n;i++){
		scanf("%s",s[i]+1);
		for(int j=1;j<=m;j++){
			if(s[i][j]=='X')xs++;
		}
	}
	vector<pair<vector<int>,pair<int,int>>> tmp;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int x=i,y=j;
			int len=1;
			int curr=0;
			int cnt=0;
			int d=0;
			vector<int> ans;
			if(s[x][y]=='X')ans.pb(0);
			int now=0;
			while(ans.size()<xs){
				x+=dir[d][0];
				y+=dir[d][1];
				curr++;
				if(curr==len){
					curr=0;
					cnt++;
					d=(d+1)%4;
					if(cnt==2){
						cnt=0;
						len++;
					}
				}
				now++;
				if(x>=1 && x<=n && y>=1 && y<=m && s[x][y]=='X')ans.pb(now);
			}
			tmp.pb({ans,{n-i+1,j}});
		}
	}
	sort(tmp.begin(),tmp.end());
	int mx=-1,sum=0;
	vector<pair<int,int>> sol;
	for(int i=0;i<tmp.size();i++){
		int ans=0;
		if(i!=0)ans=max(ans,Get(tmp[i].first,tmp[i-1].first));
		if(i+1!=tmp.size())ans=max(ans,Get(tmp[i].first,tmp[i+1].first));
		if(ans>mx){
			mx=ans;
			sol.clear();
		}
		if(ans==mx)sol.pb(tmp[i].second);
		sum+=ans;
	}
	printf("%.12lf\n",(double)sum/n/m);
	printf("%i\n",mx);
	sort(sol.begin(),sol.end());
	for(auto p:sol)printf("(%i,%i) ",p.second,p.first);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 1
X

output:

0.000000000000
0
(1,1) 

result:

ok correct!

Test #2:

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

input:

2 1
.X

output:

0.000000000000
0
(1,1) (2,1) 

result:

ok correct!

Test #3:

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

input:

2 1
X.

output:

0.000000000000
0
(1,1) (2,1) 

result:

ok correct!

Test #4:

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

input:

1 2
.
X

output:

0.000000000000
0
(1,1) (1,2) 

result:

ok correct!

Test #5:

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

input:

1 2
X
.

output:

0.000000000000
0
(1,1) (1,2) 

result:

ok correct!

Test #6:

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

input:

2 1
XX

output:

3.000000000000
3
(1,1) (2,1) 

result:

ok correct!

Test #7:

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

input:

3 3
XXX
X.X
XXX

output:

3.111111111111
5
(3,1) (3,2) 

result:

ok correct!

Test #8:

score: 0
Accepted
time: 528ms
memory: 7120kb

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.947100000000
9704
(50,1) (50,100) 

result:

ok correct!

Test #9:

score: 0
Accepted
time: 373ms
memory: 4144kb

input:

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

output:

19735.319899999999
39599
(100,1) (100,2) 

result:

ok correct!

Test #10:

score: 0
Accepted
time: 372ms
memory: 4308kb

input:

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

output:

19865.669900000001
39500
(100,1) (100,2) 

result:

ok correct!

Test #11:

score: 0
Accepted
time: 527ms
memory: 8056kb

input:

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

output:

11855.639200000000
39302
(100,99) (99,100) 

result:

ok correct!

Test #12:

score: 0
Accepted
time: 522ms
memory: 7896kb

input:

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

output:

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

result:

ok correct!

Test #13:

score: 0
Accepted
time: 31ms
memory: 4612kb

input:

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

output:

50.097945205479
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: 76ms
memory: 5164kb

input:

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

output:

100.711201079622
742
(1,1) (2,1) 

result:

ok correct!

Test #15:

score: 0
Accepted
time: 55ms
memory: 4032kb

input:

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

output:

494.497881355932
1503
(56,38) (56,39) 

result:

ok correct!

Test #16:

score: 0
Accepted
time: 114ms
memory: 4968kb

input:

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

output:

122.545311681509
387
(1,19) (19,32) 

result:

ok correct!

Test #17:

score: 0
Accepted
time: 49ms
memory: 4852kb

input:

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

output:

103.487444100447
334
(10,57) (11,57) 

result:

ok correct!

Test #18:

score: 0
Accepted
time: 197ms
memory: 4844kb

input:

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

output:

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

result:

ok correct!

Test #19:

score: 0
Accepted
time: 74ms
memory: 5244kb

input:

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

output:

79.149333333333
319
(1,39) (1,40) 

result:

ok correct!

Test #20:

score: 0
Accepted
time: 170ms
memory: 5236kb

input:

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

output:

383.808323787705
1084
(93,9) (51,51) 

result:

ok correct!

Test #21:

score: 0
Accepted
time: 143ms
memory: 5000kb

input:

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

output:

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

result:

ok correct!

Test #22:

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

input:

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

output:

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

result:

ok correct!

Test #23:

score: 0
Accepted
time: 66ms
memory: 4500kb

input:

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

output:

291.706029452626
860
(1,1) (1,50) 

result:

ok correct!

Test #24:

score: 0
Accepted
time: 85ms
memory: 4828kb

input:

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

output:

152.161880630631
512
(48,9) (48,67) 

result:

ok correct!

Test #25:

score: 0
Accepted
time: 482ms
memory: 7864kb

input:

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

output:

212.396250000000
1031
(1,67) (1,68) 

result:

ok correct!

Test #26:

score: 0
Accepted
time: 318ms
memory: 5764kb

input:

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

output:

357.121327254306
2687
(1,83) (1,84) 

result:

ok correct!

Test #27:

score: 0
Accepted
time: 247ms
memory: 5888kb

input:

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

output:

225.855523255814
975
(84,1) (85,1) 

result:

ok correct!

Test #28:

score: 0
Accepted
time: 132ms
memory: 5528kb

input:

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

output:

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

result:

ok correct!

Test #29:

score: 0
Accepted
time: 177ms
memory: 5340kb

input:

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

output:

738.974479638009
3378
(5,45) (5,56) 

result:

ok correct!

Test #30:

score: 0
Accepted
time: 305ms
memory: 4184kb

input:

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

output:

1550.390977443609
4192
(76,34) (76,96) 

result:

ok correct!

Test #31:

score: 0
Accepted
time: 87ms
memory: 4276kb

input:

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

output:

648.650216658642
2420
(16,1) (1,13) 

result:

ok correct!

Test #32:

score: 0
Accepted
time: 200ms
memory: 5360kb

input:

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

output:

207.337755102041
895
(1,97) (1,98) 

result:

ok correct!

Test #33:

score: 0
Accepted
time: 303ms
memory: 6848kb

input:

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

output:

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

result:

ok correct!

Test #34:

score: 0
Accepted
time: 94ms
memory: 4056kb

input:

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

output:

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

result:

ok correct!

Test #35:

score: 0
Accepted
time: 79ms
memory: 4640kb

input:

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

output:

142.153824036803
673
(1,74) (2,74) 

result:

ok correct!

Test #36:

score: 0
Accepted
time: 76ms
memory: 4872kb

input:

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

output:

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

result:

ok correct!

Test #37:

score: 0
Accepted
time: 65ms
memory: 5140kb

input:

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

output:

81.669984917044
314
(1,64) (1,65) 

result:

ok correct!

Test #38:

score: 0
Accepted
time: 107ms
memory: 4588kb

input:

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

output:

300.307526881720
1326
(39,93) (40,93) 

result:

ok correct!

Test #39:

score: 0
Accepted
time: 300ms
memory: 6204kb

input:

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

output:

474.068965517241
2063
(1,1) (49,1) 

result:

ok correct!

Test #40:

score: 0
Accepted
time: 103ms
memory: 4224kb

input:

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

output:

2555.367483811286
5914
(46,1) (46,2) 

result:

ok correct!

Test #41:

score: 0
Accepted
time: 143ms
memory: 4068kb

input:

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

output:

2389.200358422939
11288
(21,60) (22,60) 

result:

ok correct!

Test #42:

score: 0
Accepted
time: 229ms
memory: 5796kb

input:

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

output:

225.089160254266
803
(10,61) (11,61) 

result:

ok correct!

Test #43:

score: 0
Accepted
time: 416ms
memory: 7144kb

input:

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

output:

213.687569988802
941
(33,89) (33,90) 

result:

ok correct!

Test #44:

score: 0
Accepted
time: 252ms
memory: 5360kb

input:

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

output:

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

result:

ok correct!

Test #45:

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

input:

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

output:

67.354743083004
645
(1,1) (2,1) 

result:

ok correct!

Test #46:

score: 0
Accepted
time: 66ms
memory: 5244kb

input:

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

output:

80.041025641026
332
(64,34) (65,34) 

result:

ok correct!

Test #47:

score: 0
Accepted
time: 123ms
memory: 5532kb

input:

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

output:

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

result:

ok correct!

Test #48:

score: 0
Accepted
time: 160ms
memory: 4804kb

input:

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

output:

302.789846743295
799
(87,29) (87,58) 

result:

ok correct!

Test #49:

score: 0
Accepted
time: 31ms
memory: 4532kb

input:

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

output:

150.346912521441
930
(52,44) (53,44) 

result:

ok correct!

Test #50:

score: 0
Accepted
time: 403ms
memory: 5952kb

input:

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

output:

690.646413687212
3826
(1,96) (1,97) 

result:

ok correct!

Test #51:

score: 0
Accepted
time: 118ms
memory: 4868kb

input:

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

output:

356.974579831933
1620
(23,68) (51,68) 

result:

ok correct!

Test #52:

score: 0
Accepted
time: 387ms
memory: 4644kb

input:

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

output:

1705.102197802198
4664
(100,44) (100,90) 

result:

ok correct!

Test #53:

score: 0
Accepted
time: 182ms
memory: 4356kb

input:

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

output:

2976.142316017316
8305
(68,1) (69,1) 

result:

ok correct!

Test #54:

score: 0
Accepted
time: 25ms
memory: 4272kb

input:

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

output:

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

result:

ok correct!

Test #55:

score: 0
Accepted
time: 225ms
memory: 6028kb

input:

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

output:

179.279251700680
713
(98,56) (98,57) 

result:

ok correct!

Test #56:

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

input:

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

output:

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

result:

ok correct!

Test #57:

score: 0
Accepted
time: 166ms
memory: 5868kb

input:

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

output:

115.940570175439
390
(15,48) (79,48) 

result:

ok correct!

Test #58:

score: 0
Accepted
time: 60ms
memory: 4640kb

input:

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

output:

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

result:

ok correct!

Test #59:

score: 0
Accepted
time: 390ms
memory: 7056kb

input:

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

output:

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

result:

ok correct!

Test #60:

score: 0
Accepted
time: 367ms
memory: 6000kb

input:

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

output:

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

result:

ok correct!

Test #61:

score: 0
Accepted
time: 76ms
memory: 4604kb

input:

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

output:

164.878078078078
772
(1,7) (1,8) 

result:

ok correct!

Test #62:

score: 0
Accepted
time: 99ms
memory: 5252kb

input:

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

output:

106.012937595129
560
(1,1) (1,2) 

result:

ok correct!

Test #63:

score: 0
Accepted
time: 170ms
memory: 5948kb

input:

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

output:

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

result:

ok correct!

Test #64:

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

input:

1 2
X
X

output:

1.000000000000
1
(1,1) (1,2) 

result:

ok correct!

Test #65:

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

input:

1 3
X
.
.

output:

0.666666666667
1
(1,1) (1,2) 

result:

ok correct!

Test #66:

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

input:

1 3
.
X
.

output:

0.666666666667
1
(1,1) (1,3) 

result:

ok correct!

Test #67:

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

input:

1 3
X
X
.

output:

0.666666666667
1
(1,2) (1,3) 

result:

ok correct!

Test #68:

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

input:

1 3
.
.
X

output:

3.333333333333
5
(1,2) (1,3) 

result:

ok correct!

Test #69:

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

input:

1 3
X
.
X

output:

6.666666666667
10
(1,1) (1,3) 

result:

ok correct!

Test #70:

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

input:

1 3
.
X
X

output:

0.666666666667
1
(1,1) (1,2) 

result:

ok correct!

Test #71:

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

input:

1 3
X
X
X

output:

3.666666666667
5
(1,1) (1,2) 

result:

ok correct!

Test #72:

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

input:

1 4
X
.
.
.

output:

5.250000000000
10
(1,1) (1,2) 

result:

ok correct!

Test #73:

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

input:

1 4
.
X
.
.

output:

2.750000000000
5
(1,1) (1,4) 

result:

ok correct!

Test #74:

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

input:

1 4
X
X
.
.

output:

1.000000000000
1
(1,1) (1,2) (1,3) (1,4) 

result:

ok correct!

Test #75:

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

input:

1 4
.
.
X
.

output:

2.750000000000
5
(1,3) (1,4) 

result:

ok correct!

Test #76:

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

input:

1 4
X
.
X
.

output:

7.500000000000
10
(1,2) (1,4) 

result:

ok correct!

Test #77:

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

input:

1 4
.
X
X
.

output:

1.000000000000
1
(1,1) (1,2) (1,3) (1,4) 

result:

ok correct!

Test #78:

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

input:

1 4
X
X
X
.

output:

2.750000000000
5
(1,2) (1,3) 

result:

ok correct!

Test #79:

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

input:

1 4
.
.
.
X

output:

10.250000000000
18
(1,3) (1,4) 

result:

ok correct!

Test #80:

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

input:

1 4
X
.
.
X

output:

14.000000000000
27
(1,1) (1,4) 

result:

ok correct!

Test #81:

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

input:

1 4
.
X
.
X

output:

5.500000000000
10
(1,1) (1,3) 

result:

ok correct!

Test #82:

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

input:

1 4
X
X
.
X

output:

2.750000000000
5
(1,1) (1,4) 

result:

ok correct!

Test #83:

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

input:

1 4
.
.
X
X

output:

3.000000000000
5
(1,3) (1,4) 

result:

ok correct!

Test #84:

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

input:

1 4
X
.
X
X

output:

2.750000000000
5
(1,2) (1,4) 

result:

ok correct!

Test #85:

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

input:

1 4
.
X
X
X

output:

2.750000000000
5
(1,1) (1,2) 

result:

ok correct!

Test #86:

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

input:

1 4
X
X
X
X

output:

6.500000000000
10
(1,2) (1,3) 

result:

ok correct!

Test #87:

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

input:

2 2
X.
..

output:

3.750000000000
7
(2,1) (2,2) 

result:

ok correct!

Test #88:

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

input:

2 2
.X
..

output:

1.250000000000
2
(1,1) (1,2) 

result:

ok correct!

Test #89:

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

input:

2 2
XX
..

output:

2.500000000000
3
(1,2) (2,2) 

result:

ok correct!

Test #90:

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

input:

2 2
..
X.

output:

4.250000000000
6
(2,1) (2,2) 

result:

ok correct!

Test #91:

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

input:

2 2
X.
X.

output:

3.500000000000
6
(2,1) (2,2) 

result:

ok correct!

Test #92:

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

input:

2 2
.X
X.

output:

1.500000000000
2
(1,1) (2,2) 

result:

ok correct!

Test #93:

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

input:

2 2
XX
X.

output:

1.750000000000
3
(1,2) (2,2) 

result:

ok correct!

Test #94:

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

input:

2 2
..
.X

output:

2.750000000000
4
(1,2) (2,2) 

result:

ok correct!

Test #95:

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

input:

2 2
X.
.X

output:

2.500000000000
4
(2,1) (1,2) 

result:

ok correct!

Test #96:

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

input:

2 2
.X
.X

output:

1.500000000000
2
(1,1) (1,2) 

result:

ok correct!

Test #97:

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

input:

2 2
XX
.X

output:

1.750000000000
3
(1,2) (2,2) 

result:

ok correct!

Test #98:

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

input:

2 2
..
XX

output:

3.500000000000
4
(1,2) (2,2) 

result:

ok correct!

Test #99:

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

input:

2 2
X.
XX

output:

2.250000000000
4
(2,1) (1,2) 

result:

ok correct!

Test #100:

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

input:

2 2
.X
XX

output:

1.250000000000
2
(1,1) (2,2) 

result:

ok correct!

Test #101:

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

input:

2 2
XX
XX

output:

2.500000000000
3
(1,2) (2,2) 

result:

ok correct!

Test #102:

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

input:

3 1
X..

output:

4.666666666667
7
(2,1) (3,1) 

result:

ok correct!

Test #103:

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

input:

3 1
.X.

output:

2.000000000000
3
(1,1) (3,1) 

result:

ok correct!

Test #104:

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

input:

3 1
XX.

output:

2.000000000000
3
(1,1) (2,1) 

result:

ok correct!

Test #105:

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

input:

3 1
..X

output:

2.000000000000
3
(1,1) (2,1) 

result:

ok correct!

Test #106:

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

input:

3 1
X.X

output:

9.333333333333
14
(1,1) (3,1) 

result:

ok correct!

Test #107:

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

input:

3 1
.XX

output:

2.000000000000
3
(2,1) (3,1) 

result:

ok correct!

Test #108:

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

input:

3 1
XXX

output:

5.666666666667
7
(1,1) (2,1) 

result:

ok correct!

Test #109:

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

input:

4 1
X...

output:

12.750000000000
22
(3,1) (4,1) 

result:

ok correct!

Test #110:

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

input:

4 1
.X..

output:

4.250000000000
7
(3,1) (4,1) 

result:

ok correct!

Test #111:

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

input:

4 1
XX..

output:

5.000000000000
7
(3,1) (4,1) 

result:

ok correct!

Test #112:

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

input:

4 1
..X.

output:

4.250000000000
7
(1,1) (4,1) 

result:

ok correct!

Test #113:

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

input:

4 1
X.X.

output:

8.500000000000
14
(1,1) (3,1) 

result:

ok correct!

Test #114:

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

input:

4 1
.XX.

output:

3.000000000000
3
(1,1) (2,1) (3,1) (4,1) 

result:

ok correct!

Test #115:

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

input:

4 1
XXX.

output:

4.250000000000
7
(1,1) (2,1) 

result:

ok correct!

Test #116:

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

input:

4 1
...X

output:

7.750000000000
14
(1,1) (2,1) 

result:

ok correct!

Test #117:

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

input:

4 1
X..X

output:

18.000000000000
33
(1,1) (4,1) 

result:

ok correct!

Test #118:

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

input:

4 1
.X.X

output:

10.500000000000
14
(2,1) (4,1) 

result:

ok correct!

Test #119:

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

input:

4 1
XX.X

output:

4.250000000000
7
(2,1) (4,1) 

result:

ok correct!

Test #120:

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

input:

4 1
..XX

output:

3.000000000000
3
(1,1) (2,1) (3,1) (4,1) 

result:

ok correct!

Test #121:

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

input:

4 1
X.XX

output:

4.250000000000
7
(1,1) (4,1) 

result:

ok correct!

Test #122:

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

input:

4 1
.XXX

output:

4.250000000000
7
(2,1) (3,1) 

result:

ok correct!

Test #123:

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

input:

4 1
XXXX

output:

9.500000000000
14
(2,1) (3,1) 

result:

ok correct!

Test #124:

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

input:

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

output:

13274.590000000000
38710
(99,1) (100,1) 

result:

ok correct!

Test #125:

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

input:

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

output:

13076.629999999999
38318
(1,1) (2,1) 

result:

ok correct!

Test #126:

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

input:

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

output:

3356.010000000000
9751
(1,1) (100,1) 

result:

ok correct!

Test #127:

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

input:

100 1
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

output:

3457.500000000000
9950
(50,1) (51,1) 

result:

ok correct!

Test #128:

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

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.940000000000
9950
(49,1) (51,1) 

result:

ok correct!

Test #129:

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

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.070000000000
9751
(49,1) (51,1) 

result:

ok correct!

Test #130:

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

input:

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

output:

12977.650000000000
38122
(1,1) (1,2) 

result:

ok correct!

Test #131:

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

input:

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

output:

13175.610000000001
38514
(1,99) (1,100) 

result:

ok correct!

Test #132:

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

input:

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

output:

3306.030000000000
9653
(1,99) (1,100) 

result:

ok correct!

Test #133:

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

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.500000000000
9850
(1,50) (1,51) 

result:

ok correct!

Test #134:

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

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.020000000000
9850
(1,50) (1,52) 

result:

ok correct!

Test #135:

score: 0
Accepted
time: 8ms
memory: 4004kb

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.110000000000
9654
(2,49) (2,51) 

result:

ok correct!

Test #136:

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

input:

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

output:

58.080000000000
95
(5,10) (6,10) 

result:

ok correct!

Test #137:

score: 0
Accepted
time: 483ms
memory: 8020kb

input:

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

output:

13878.927500000000
38908
(99,1) (100,1) 

result:

ok correct!

Test #138:

score: 0
Accepted
time: 467ms
memory: 8000kb

input:

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

output:

14059.272499999999
39302
(99,100) (100,100) 

result:

ok correct!

Test #139:

score: 0
Accepted
time: 475ms
memory: 8028kb

input:

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

output:

14132.282499999999
39500
(100,1) (100,2) 

result:

ok correct!

Test #140:

score: 0
Accepted
time: 472ms
memory: 7980kb

input:

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

output:

13951.432500000001
39104
(1,99) (1,100) 

result:

ok correct!

Test #141:

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

input:

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

output:

19733.339899999999
39302
(99,100) (100,100) 

result:

ok correct!

Test #142:

score: 0
Accepted
time: 365ms
memory: 4144kb

input:

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

output:

19601.009900000001
39104
(1,99) (1,100) 

result:

ok correct!

Test #143:

score: 0
Accepted
time: 104ms
memory: 4428kb

input:

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

output:

5001.489900000000
10098
(99,100) (100,100) 

result:

ok correct!

Test #144:

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

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.812500000000
31
(13,5) (15,18) 

result:

ok correct!

Test #145:

score: 0
Accepted
time: 37ms
memory: 4976kb

input:

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

output:

60.830800000000
195
(28,1) (1,35) 

result:

ok correct!

Test #146:

score: 0
Accepted
time: 525ms
memory: 7900kb

input:

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

output:

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

result:

ok correct!

Extra Test:

score: 0
Extra Test Passed