QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#392060#5112. Where Am I?nocrizAC ✓539ms8188kbC++141.5kb2024-04-17 04:10:152024-04-17 04:10:16

Judging History

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

  • [2024-04-17 04:10:16]
  • 评测
  • 测评结果:AC
  • 用时:539ms
  • 内存:8188kb
  • [2024-04-17 04:10:15]
  • 提交

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: 1ms
memory: 3812kb

input:

1 1
X

output:

0.000000000000
0
(1,1) 

result:

ok correct!

Test #2:

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

input:

2 1
.X

output:

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

result:

ok correct!

Test #3:

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

input:

2 1
X.

output:

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

result:

ok correct!

Test #4:

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

input:

1 2
.
X

output:

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

result:

ok correct!

Test #5:

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

input:

1 2
X
.

output:

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

result:

ok correct!

Test #6:

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

input:

2 1
XX

output:

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

result:

ok correct!

Test #7:

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

input:

3 3
XXX
X.X
XXX

output:

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

result:

ok correct!

Test #8:

score: 0
Accepted
time: 534ms
memory: 7404kb

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: 386ms
memory: 4228kb

input:

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

output:

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

result:

ok correct!

Test #10:

score: 0
Accepted
time: 383ms
memory: 4420kb

input:

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

output:

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

result:

ok correct!

Test #11:

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

input:

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

output:

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

result:

ok correct!

Test #12:

score: 0
Accepted
time: 533ms
memory: 7976kb

input:

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

output:

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

result:

ok correct!

Test #13:

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

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: 80ms
memory: 5088kb

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: 58ms
memory: 4180kb

input:

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

output:

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

result:

ok correct!

Test #16:

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

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: 52ms
memory: 4628kb

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: 202ms
memory: 4640kb

input:

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

output:

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

result:

ok correct!

Test #19:

score: 0
Accepted
time: 73ms
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: 198ms
memory: 5304kb

input:

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

output:

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

result:

ok correct!

Test #21:

score: 0
Accepted
time: 147ms
memory: 4904kb

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: 4768kb

input:

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

output:

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

result:

ok correct!

Test #23:

score: 0
Accepted
time: 69ms
memory: 4320kb

input:

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

output:

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

result:

ok correct!

Test #24:

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

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: 499ms
memory: 7816kb

input:

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

output:

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

result:

ok correct!

Test #26:

score: 0
Accepted
time: 330ms
memory: 5728kb

input:

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

output:

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

result:

ok correct!

Test #27:

score: 0
Accepted
time: 255ms
memory: 5856kb

input:

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

output:

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

result:

ok correct!

Test #28:

score: 0
Accepted
time: 137ms
memory: 5460kb

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: 173ms
memory: 5104kb

input:

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

output:

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

result:

ok correct!

Test #30:

score: 0
Accepted
time: 306ms
memory: 4228kb

input:

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

output:

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

result:

ok correct!

Test #31:

score: 0
Accepted
time: 86ms
memory: 4396kb

input:

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

output:

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

result:

ok correct!

Test #32:

score: 0
Accepted
time: 202ms
memory: 5412kb

input:

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

output:

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

result:

ok correct!

Test #33:

score: 0
Accepted
time: 317ms
memory: 6744kb

input:

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

output:

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

result:

ok correct!

Test #34:

score: 0
Accepted
time: 97ms
memory: 4040kb

input:

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

output:

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

result:

ok correct!

Test #35:

score: 0
Accepted
time: 89ms
memory: 4688kb

input:

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

output:

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

result:

ok correct!

Test #36:

score: 0
Accepted
time: 75ms
memory: 4860kb

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: 71ms
memory: 5192kb

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: 119ms
memory: 4228kb

input:

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

output:

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

result:

ok correct!

Test #39:

score: 0
Accepted
time: 322ms
memory: 6368kb

input:

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

output:

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

result:

ok correct!

Test #40:

score: 0
Accepted
time: 98ms
memory: 4240kb

input:

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

output:

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

result:

ok correct!

Test #41:

score: 0
Accepted
time: 145ms
memory: 4292kb

input:

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

output:

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

result:

ok correct!

Test #42:

score: 0
Accepted
time: 243ms
memory: 5616kb

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: 431ms
memory: 7192kb

input:

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

output:

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

result:

ok correct!

Test #44:

score: 0
Accepted
time: 279ms
memory: 5476kb

input:

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

output:

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

result:

ok correct!

Test #45:

score: 0
Accepted
time: 27ms
memory: 4544kb

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: 69ms
memory: 5156kb

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: 121ms
memory: 5464kb

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: 172ms
memory: 4808kb

input:

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

output:

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

result:

ok correct!

Test #49:

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

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: 411ms
memory: 5936kb

input:

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

output:

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

result:

ok correct!

Test #51:

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

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: 393ms
memory: 4820kb

input:

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

output:

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

result:

ok correct!

Test #53:

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

input:

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

output:

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

result:

ok correct!

Test #54:

score: 0
Accepted
time: 22ms
memory: 4424kb

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: 228ms
memory: 6308kb

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: 41ms
memory: 4568kb

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: 172ms
memory: 5540kb

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: 62ms
memory: 4648kb

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: 395ms
memory: 7276kb

input:

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

output:

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

result:

ok correct!

Test #60:

score: 0
Accepted
time: 374ms
memory: 5828kb

input:

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

output:

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

result:

ok correct!

Test #61:

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

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: 102ms
memory: 5468kb

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: 178ms
memory: 5652kb

input:

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

output:

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

result:

ok correct!

Test #64:

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

input:

1 2
X
X

output:

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

result:

ok correct!

Test #65:

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

input:

1 3
X
.
.

output:

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

result:

ok correct!

Test #66:

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

input:

1 3
.
X
.

output:

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

result:

ok correct!

Test #67:

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

input:

1 3
X
X
.

output:

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

result:

ok correct!

Test #68:

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

input:

1 3
.
.
X

output:

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

result:

ok correct!

Test #69:

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

input:

1 3
X
.
X

output:

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

result:

ok correct!

Test #70:

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

input:

1 3
.
X
X

output:

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

result:

ok correct!

Test #71:

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

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: 3884kb

input:

1 4
X
.
.
.

output:

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

result:

ok correct!

Test #73:

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

input:

1 4
.
X
.
.

output:

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

result:

ok correct!

Test #74:

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

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: 3804kb

input:

1 4
.
.
X
.

output:

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

result:

ok correct!

Test #76:

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

input:

1 4
X
.
X
.

output:

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

result:

ok correct!

Test #77:

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

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: 3928kb

input:

1 4
X
X
X
.

output:

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

result:

ok correct!

Test #79:

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

input:

1 4
.
.
.
X

output:

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

result:

ok correct!

Test #80:

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

input:

1 4
X
.
.
X

output:

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

result:

ok correct!

Test #81:

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

input:

1 4
.
X
.
X

output:

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

result:

ok correct!

Test #82:

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

input:

1 4
X
X
.
X

output:

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

result:

ok correct!

Test #83:

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

input:

1 4
.
.
X
X

output:

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

result:

ok correct!

Test #84:

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

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: 3900kb

input:

1 4
.
X
X
X

output:

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

result:

ok correct!

Test #86:

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

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: 3972kb

input:

2 2
X.
..

output:

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

result:

ok correct!

Test #88:

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

input:

2 2
.X
..

output:

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

result:

ok correct!

Test #89:

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

input:

2 2
XX
..

output:

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

result:

ok correct!

Test #90:

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

input:

2 2
..
X.

output:

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

result:

ok correct!

Test #91:

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

input:

2 2
X.
X.

output:

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

result:

ok correct!

Test #92:

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

input:

2 2
.X
X.

output:

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

result:

ok correct!

Test #93:

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

input:

2 2
XX
X.

output:

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

result:

ok correct!

Test #94:

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

input:

2 2
..
.X

output:

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

result:

ok correct!

Test #95:

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

input:

2 2
X.
.X

output:

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

result:

ok correct!

Test #96:

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

input:

2 2
.X
.X

output:

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

result:

ok correct!

Test #97:

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

input:

2 2
XX
.X

output:

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

result:

ok correct!

Test #98:

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

input:

2 2
..
XX

output:

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

result:

ok correct!

Test #99:

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

input:

2 2
X.
XX

output:

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

result:

ok correct!

Test #100:

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

input:

2 2
.X
XX

output:

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

result:

ok correct!

Test #101:

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

input:

2 2
XX
XX

output:

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

result:

ok correct!

Test #102:

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

input:

3 1
X..

output:

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

result:

ok correct!

Test #103:

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

input:

3 1
.X.

output:

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

result:

ok correct!

Test #104:

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

input:

3 1
XX.

output:

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

result:

ok correct!

Test #105:

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

input:

3 1
..X

output:

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

result:

ok correct!

Test #106:

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

input:

3 1
X.X

output:

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

result:

ok correct!

Test #107:

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

input:

3 1
.XX

output:

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

result:

ok correct!

Test #108:

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

input:

3 1
XXX

output:

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

result:

ok correct!

Test #109:

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

input:

4 1
X...

output:

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

result:

ok correct!

Test #110:

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

input:

4 1
.X..

output:

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

result:

ok correct!

Test #111:

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

input:

4 1
XX..

output:

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

result:

ok correct!

Test #112:

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

input:

4 1
..X.

output:

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

result:

ok correct!

Test #113:

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

input:

4 1
X.X.

output:

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

result:

ok correct!

Test #114:

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

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: 1ms
memory: 4100kb

input:

4 1
XXX.

output:

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

result:

ok correct!

Test #116:

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

input:

4 1
...X

output:

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

result:

ok correct!

Test #117:

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

input:

4 1
X..X

output:

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

result:

ok correct!

Test #118:

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

input:

4 1
.X.X

output:

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

result:

ok correct!

Test #119:

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

input:

4 1
XX.X

output:

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

result:

ok correct!

Test #120:

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

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: 1ms
memory: 3968kb

input:

4 1
X.XX

output:

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

result:

ok correct!

Test #122:

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

input:

4 1
.XXX

output:

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

result:

ok correct!

Test #123:

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

input:

4 1
XXXX

output:

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

result:

ok correct!

Test #124:

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

input:

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

output:

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

result:

ok correct!

Test #125:

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

input:

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

output:

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

result:

ok correct!

Test #126:

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

input:

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

output:

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

result:

ok correct!

Test #127:

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

input:

100 1
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

output:

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

result:

ok correct!

Test #128:

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

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: 4ms
memory: 3904kb

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: 3ms
memory: 3984kb

input:

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

output:

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

result:

ok correct!

Test #131:

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

input:

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

output:

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

result:

ok correct!

Test #132:

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

input:

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

output:

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

result:

ok correct!

Test #133:

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

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: 5ms
memory: 3940kb

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: 9ms
memory: 4008kb

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: 3864kb

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: 487ms
memory: 7876kb

input:

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

output:

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

result:

ok correct!

Test #138:

score: 0
Accepted
time: 486ms
memory: 7892kb

input:

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

output:

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

result:

ok correct!

Test #139:

score: 0
Accepted
time: 506ms
memory: 8140kb

input:

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

output:

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

result:

ok correct!

Test #140:

score: 0
Accepted
time: 493ms
memory: 8188kb

input:

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

output:

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

result:

ok correct!

Test #141:

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

input:

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

output:

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

result:

ok correct!

Test #142:

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

input:

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

output:

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

result:

ok correct!

Test #143:

score: 0
Accepted
time: 108ms
memory: 4132kb

input:

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

output:

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

result:

ok correct!

Test #144:

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

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: 41ms
memory: 4828kb

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: 527ms
memory: 7980kb

input:

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

output:

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

result:

ok correct!

Extra Test:

score: 0
Extra Test Passed