QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#355338#5112. Where Am I?ucup-team052#AC ✓23ms9616kbC++232.7kb2024-03-16 16:09:332024-03-16 16:09:33

Judging History

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

  • [2024-03-16 16:09:33]
  • 评测
  • 测评结果:AC
  • 用时:23ms
  • 内存:9616kb
  • [2024-03-16 16:09:33]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define N 105
int ans[N][N];
char _s[N][N];
char s[N][N];
int n,m;
vector<int> pos[N][N];
pair<int,int> ids[N*N];
vector<pair<int,int>> xs;
int calc(int dx,int dy)
{
	int mnd=max(abs(dx),abs(dy));
	if(dx==-mnd&&dy!=-mnd) return (mnd*2-1)*(mnd*2-1)+dy+mnd-1;
	else if(dy==mnd) return (mnd*2-1)*(mnd*2-1)+2*mnd+dx+mnd-1;
	else if(dx==mnd) return (mnd*2-1)*(mnd*2-1)+4*mnd+mnd-dy-1;
	else return (mnd*2-1)*(mnd*2-1)+6*mnd+mnd-dx-1;
}
int cmp(pair<int,int> x,pair<int,int> y)
{
	const vector<int> &a=pos[x.first][x.second];
	const vector<int> &b=pos[y.first][y.second];
	for(int i=0;i<(int)a.size();i++)
	{
		if(a[i]!=b[i]) return a[i]>b[i];
	}
	assert(0);
}
int getdif(pair<int,int> x,pair<int,int> y)
{
	const vector<int> &a=pos[x.first][x.second];
	const vector<int> &b=pos[y.first][y.second];
	for(int i=0;i<(int)a.size();i++)
	{
		if(a[i]!=b[i]) return min(a[i],b[i]);
	}
	assert(0);
}
signed main()
{
#ifdef xay5421
	freopen("a.in","r",stdin);
#endif
	cin>>n>>m;
	swap(n,m);
	for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(s[i][j]=='X') xs.emplace_back(i,j);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			for(auto [x,y]:xs) pos[i][j].push_back(calc(x-i,y-j));
			sort(pos[i][j].begin(),pos[i][j].end());
			ids[(i-1)*m+j]=make_pair(i,j);
		}
	}
	sort(ids+1,ids+n*m+1,cmp);
	long long sum=0; vector<pair<int,int>> mxv; int mxw=-1;
	for(int i=1;i<=n*m;i++)
	{
		auto [x,y]=ids[i];
		if(i!=1)
		{
			ans[x][y]=max(ans[x][y],getdif(ids[i],ids[i-1]));
		}
		if(i!=n*m)
		{
			ans[x][y]=max(ans[x][y],getdif(ids[i],ids[i+1]));
		}
		sum+=ans[x][y];
		if(ans[x][y]>mxw) mxw=ans[x][y],mxv.clear();
		if(ans[x][y]==mxw) mxv.emplace_back(n-x+1,y);
		// printf("%d %d : %d - ",x,y,ans[x][y]);
		// for(int w:pos[x][y]) printf("%d ",w);
		// cout<<"\n";
	}
	printf("%.5lf\n",(double)sum/n/m);
	printf("%d\n",mxw);
	sort(mxv.begin(),mxv.end());
	for(auto [x,y]:mxv) printf("(%d,%d) ",y,x);
	cout<<"\n";
	return 0;
}

/*
5 3 : 2 - 0 2 26 27 54 
4 4 : 6 - 0 6 28 28 51 
4 1 : 11 - 0 11 15 33 57 
2 2 : 16 - 0 16 19 32 38 
1 5 : 16 - 0 40 50 70 81 
3 2 : 6 - 1 6 15 17 31 
5 4 : 9 - 1 9 25 52 53 
5 1 : 14 - 1 14 28 32 56 
2 5 : 14 - 1 19 41 51 82 
3 1 : 5 - 2 5 16 34 58 
2 4 : 5 - 2 18 26 40 49 
4 3 : 5 - 3 5 9 26 29 
5 2 : 10 - 3 10 13 27 55 
2 1 : 18 - 3 18 35 37 59 
1 4 : 18 - 3 25 39 42 69 
4 2 : 9 - 4 9 10 14 30 
3 3 : 10 - 4 10 12 18 25 
1 1 : 10 - 4 36 39 60 66 
3 4 : 11 - 5 11 19 27 50 
1 2 : 11 - 5 33 37 40 67 
3 5 : 10 - 6 10 20 52 83 
1 3 : 10 - 6 14 38 41 68 
2 3 : 13 - 9 13 17 20 39 
4 5 : 13 - 9 25 27 53 84 
5 5 : 9 - 10 26 52 54 85 
10.44000
18
(1,4) (4,5)
*/

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3848kb

input:

1 1
X

output:

0.00000
0
(1,1) 

result:

ok correct!

Test #2:

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

input:

2 1
.X

output:

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

result:

ok correct!

Test #3:

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

input:

2 1
X.

output:

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

result:

ok correct!

Test #4:

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

input:

1 2
.
X

output:

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

result:

ok correct!

Test #5:

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

input:

1 2
X
.

output:

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

result:

ok correct!

Test #6:

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

input:

2 1
XX

output:

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

result:

ok correct!

Test #7:

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

input:

3 3
XXX
X.X
XXX

output:

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

result:

ok correct!

Test #8:

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

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: 2ms
memory: 4488kb

input:

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

output:

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

result:

ok correct!

Test #10:

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

input:

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

output:

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

result:

ok correct!

Test #11:

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

input:

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

output:

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

result:

ok correct!

Test #12:

score: 0
Accepted
time: 18ms
memory: 9332kb

input:

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

output:

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

result:

ok correct!

Test #13:

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

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

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: 2ms
memory: 4496kb

input:

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

output:

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

result:

ok correct!

Test #16:

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

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: 6ms
memory: 5784kb

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

input:

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

output:

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

result:

ok correct!

Test #19:

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

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: 8ms
memory: 5404kb

input:

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

output:

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

result:

ok correct!

Test #21:

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

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

input:

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

output:

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

result:

ok correct!

Test #23:

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

input:

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

output:

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

result:

ok correct!

Test #24:

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

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: 17ms
memory: 9120kb

input:

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

output:

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

result:

ok correct!

Test #26:

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

input:

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

output:

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

result:

ok correct!

Test #27:

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

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

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

input:

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

output:

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

result:

ok correct!

Test #30:

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

input:

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

output:

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

result:

ok correct!

Test #31:

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

input:

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

output:

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

result:

ok correct!

Test #32:

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

input:

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

output:

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

result:

ok correct!

Test #33:

score: 0
Accepted
time: 14ms
memory: 7860kb

input:

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

output:

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

result:

ok correct!

Test #34:

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

input:

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

output:

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

result:

ok correct!

Test #35:

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

input:

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

output:

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

result:

ok correct!

Test #36:

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

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: 8ms
memory: 5724kb

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

input:

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

output:

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

result:

ok correct!

Test #39:

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

input:

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

output:

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

result:

ok correct!

Test #40:

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

input:

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

output:

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

result:

ok correct!

Test #41:

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

input:

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

output:

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

result:

ok correct!

Test #42:

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

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: 17ms
memory: 8832kb

input:

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

output:

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

result:

ok correct!

Test #44:

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

input:

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

output:

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

result:

ok correct!

Test #45:

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

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: 11ms
memory: 5696kb

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: 10ms
memory: 6388kb

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

input:

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

output:

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

result:

ok correct!

Test #49:

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

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: 10ms
memory: 6868kb

input:

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

output:

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

result:

ok correct!

Test #51:

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

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

input:

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

output:

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

result:

ok correct!

Test #53:

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

input:

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

output:

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

result:

ok correct!

Test #54:

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

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: 15ms
memory: 7104kb

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

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: 6ms
memory: 6276kb

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

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

input:

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

output:

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

result:

ok correct!

Test #60:

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

input:

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

output:

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

result:

ok correct!

Test #61:

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

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: 8ms
memory: 6136kb

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: 8ms
memory: 6656kb

input:

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

output:

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

result:

ok correct!

Test #64:

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

input:

1 2
X
X

output:

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

result:

ok correct!

Test #65:

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

input:

1 3
X
.
.

output:

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

result:

ok correct!

Test #66:

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

input:

1 3
.
X
.

output:

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

result:

ok correct!

Test #67:

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

input:

1 3
X
X
.

output:

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

result:

ok correct!

Test #68:

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

input:

1 3
.
.
X

output:

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

result:

ok correct!

Test #69:

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

input:

1 3
X
.
X

output:

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

result:

ok correct!

Test #70:

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

input:

1 3
.
X
X

output:

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

result:

ok correct!

Test #71:

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

input:

1 3
X
X
X

output:

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

result:

ok correct!

Test #72:

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

input:

1 4
X
.
.
.

output:

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

result:

ok correct!

Test #73:

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

input:

1 4
.
X
.
.

output:

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

result:

ok correct!

Test #74:

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

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

input:

1 4
.
.
X
.

output:

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

result:

ok correct!

Test #76:

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

input:

1 4
X
.
X
.

output:

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

result:

ok correct!

Test #77:

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

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

input:

1 4
X
X
X
.

output:

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

result:

ok correct!

Test #79:

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

input:

1 4
.
.
.
X

output:

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

result:

ok correct!

Test #80:

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

input:

1 4
X
.
.
X

output:

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

result:

ok correct!

Test #81:

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

input:

1 4
.
X
.
X

output:

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

result:

ok correct!

Test #82:

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

input:

1 4
X
X
.
X

output:

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

result:

ok correct!

Test #83:

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

input:

1 4
.
.
X
X

output:

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

result:

ok correct!

Test #84:

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

input:

1 4
X
.
X
X

output:

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

result:

ok correct!

Test #85:

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

input:

1 4
.
X
X
X

output:

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

result:

ok correct!

Test #86:

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

input:

1 4
X
X
X
X

output:

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

result:

ok correct!

Test #87:

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

input:

2 2
X.
..

output:

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

result:

ok correct!

Test #88:

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

input:

2 2
.X
..

output:

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

result:

ok correct!

Test #89:

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

input:

2 2
XX
..

output:

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

result:

ok correct!

Test #90:

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

input:

2 2
..
X.

output:

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

result:

ok correct!

Test #91:

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

input:

2 2
X.
X.

output:

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

result:

ok correct!

Test #92:

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

input:

2 2
.X
X.

output:

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

result:

ok correct!

Test #93:

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

input:

2 2
XX
X.

output:

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

result:

ok correct!

Test #94:

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

input:

2 2
..
.X

output:

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

result:

ok correct!

Test #95:

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

input:

2 2
X.
.X

output:

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

result:

ok correct!

Test #96:

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

input:

2 2
.X
.X

output:

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

result:

ok correct!

Test #97:

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

input:

2 2
XX
.X

output:

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

result:

ok correct!

Test #98:

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

input:

2 2
..
XX

output:

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

result:

ok correct!

Test #99:

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

input:

2 2
X.
XX

output:

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

result:

ok correct!

Test #100:

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

input:

2 2
.X
XX

output:

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

result:

ok correct!

Test #101:

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

input:

2 2
XX
XX

output:

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

result:

ok correct!

Test #102:

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

input:

3 1
X..

output:

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

result:

ok correct!

Test #103:

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

input:

3 1
.X.

output:

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

result:

ok correct!

Test #104:

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

input:

3 1
XX.

output:

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

result:

ok correct!

Test #105:

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

input:

3 1
..X

output:

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

result:

ok correct!

Test #106:

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

input:

3 1
X.X

output:

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

result:

ok correct!

Test #107:

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

input:

3 1
.XX

output:

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

result:

ok correct!

Test #108:

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

input:

3 1
XXX

output:

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

result:

ok correct!

Test #109:

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

input:

4 1
X...

output:

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

result:

ok correct!

Test #110:

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

input:

4 1
.X..

output:

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

result:

ok correct!

Test #111:

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

input:

4 1
XX..

output:

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

result:

ok correct!

Test #112:

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

input:

4 1
..X.

output:

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

result:

ok correct!

Test #113:

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

input:

4 1
X.X.

output:

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

result:

ok correct!

Test #114:

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

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

input:

4 1
XXX.

output:

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

result:

ok correct!

Test #116:

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

input:

4 1
...X

output:

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

result:

ok correct!

Test #117:

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

input:

4 1
X..X

output:

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

result:

ok correct!

Test #118:

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

input:

4 1
.X.X

output:

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

result:

ok correct!

Test #119:

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

input:

4 1
XX.X

output:

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

result:

ok correct!

Test #120:

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

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

input:

4 1
X.XX

output:

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

result:

ok correct!

Test #122:

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

input:

4 1
.XXX

output:

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

result:

ok correct!

Test #123:

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

input:

4 1
XXXX

output:

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

result:

ok correct!

Test #124:

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

input:

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

output:

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

result:

ok correct!

Test #125:

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

input:

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

output:

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

result:

ok correct!

Test #126:

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

input:

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

output:

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

result:

ok correct!

Test #127:

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

input:

100 1
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

output:

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

result:

ok correct!

Test #128:

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

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

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: 0ms
memory: 4164kb

input:

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

output:

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

result:

ok correct!

Test #131:

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

input:

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

output:

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

result:

ok correct!

Test #132:

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

input:

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

output:

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

result:

ok correct!

Test #133:

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

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

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

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

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: 14ms
memory: 9580kb

input:

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

output:

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

result:

ok correct!

Test #138:

score: 0
Accepted
time: 11ms
memory: 9616kb

input:

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

output:

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

result:

ok correct!

Test #139:

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

input:

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

output:

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

result:

ok correct!

Test #140:

score: 0
Accepted
time: 20ms
memory: 9564kb

input:

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

output:

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

result:

ok correct!

Test #141:

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

input:

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

output:

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

result:

ok correct!

Test #142:

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

input:

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

output:

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

result:

ok correct!

Test #143:

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

input:

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

output:

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

result:

ok correct!

Test #144:

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

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

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: 23ms
memory: 9380kb

input:

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

output:

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

result:

ok correct!

Extra Test:

score: 0
Extra Test Passed