QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#96686#5112. Where Am I?marcoskAC ✓117ms100716kbC++232.0kb2023-04-15 02:55:532023-04-15 02:55:55

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-15 02:55:55]
  • 评测
  • 测评结果:AC
  • 用时:117ms
  • 内存:100716kb
  • [2023-04-15 02:55:53]
  • 提交

answer

#include <bits/stdc++.h>
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
#define pb push_back
#define ALL(s) s.begin(),s.end()
#define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define SZ(s) int(s.size())
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;

int get(int x, int y){
	int df=max(abs(x),abs(y));
	if(!df) return 1;
	
	int ans=(2*df-1)*(2*df-1);
	
	if(y==df && x!=-df) return ans+df+x;
	
	ans+=2*df;
	if(x==df && y!=df) return ans+df-y;
	
	ans+=2*df;
	if(y==-df && x!=df) return ans+df-x;
	
	ans+=2*df;
	if(x==-df && y!=-df) return ans+df+y;

	assert(0);
}

vector<int> get(vector<ii> &v, int x, int y){
	vector<int> wh;
	fore(i,0,SZ(v)) wh.pb(get(v[i].snd-y, x-v[i].fst));
	sort(ALL(wh));
	for(int i=SZ(wh)-1;i>=1;i--) wh[i]-=wh[i-1];
	return wh;
}

const int MAXN=1e6+10;
map<int,int> t[MAXN];
int idd=1,am[MAXN];

void add(vector<int> &v){
	int now=0;
	for(auto x:v){
		if(!t[now].count(x)) t[now][x]=idd++;
		now=t[now][x];
		am[now]++;
	}
}

int get(vector<int> &v){
	int now=0,sz=0;
	for(auto x:v){
		int to=t[now][x];
		if(am[to]==1){
			//con uno mas grande
			int ans=sz+x;
			
			auto it=t[now].lower_bound(x);
			if(it!=t[now].begin() && next(it)==t[now].end()) ans=sz+(--it)->fst;
			
			return ans;
		}
		now=to;
		sz+=x;
	}
	
	assert(0);
}

int main(){FIN;
	int n,m; cin>>m>>n;
	vector<ii> v;
	fore(i,0,n){
		string s; cin>>s;
		fore(j,0,m) if(s[j]=='X') v.pb({i,j});
	}
	
	vector<int> val;
	fore(i,0,n) fore(j,0,m){
		auto now=get(v,i,j);
		add(now);
	}
	
	ll res=0;
	int mx=0;
	vector<ii> ans;
	fore(i,0,n) fore(j,0,m){
		auto now=get(v,i,j);
		int val=get(now)-1;
		if(val>mx) mx=val, ans={{j,n-i-1}};
		else if(val==mx) ans.pb({j,n-i-1});
		res+=val;
	}
	
	for(auto &x:ans) swap(x.fst,x.snd);
	sort(ALL(ans));
	for(auto &x:ans) swap(x.fst,x.snd);
	
	cout<<fixed<<setprecision(10)<<1.*res/(n*m)<<"\n";
	cout<<mx<<"\n";
	for(auto x:ans)cout<<"("<<x.fst+1<<","<<x.snd+1<<") ";cout<<"\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 51204kb

input:

1 1
X

output:

0.0000000000
0
(1,1) 

result:

ok correct!

Test #2:

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

input:

2 1
.X

output:

0.0000000000
0
(1,1) (2,1) 

result:

ok correct!

Test #3:

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

input:

2 1
X.

output:

0.0000000000
0
(1,1) (2,1) 

result:

ok correct!

Test #4:

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

input:

1 2
.
X

output:

0.0000000000
0
(1,1) (1,2) 

result:

ok correct!

Test #5:

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

input:

1 2
X
.

output:

0.0000000000
0
(1,1) (1,2) 

result:

ok correct!

Test #6:

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

input:

2 1
XX

output:

3.0000000000
3
(1,1) (2,1) 

result:

ok correct!

Test #7:

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

input:

3 3
XXX
X.X
XXX

output:

3.1111111111
5
(3,1) (3,2) 

result:

ok correct!

Test #8:

score: 0
Accepted
time: 81ms
memory: 86504kb

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

result:

ok correct!

Test #9:

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

input:

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

output:

19735.3199000000
39599
(100,1) (100,2) 

result:

ok correct!

Test #10:

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

input:

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

output:

19865.6699000000
39500
(100,1) (100,2) 

result:

ok correct!

Test #11:

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

input:

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

output:

11855.6392000000
39302
(100,99) (99,100) 

result:

ok correct!

Test #12:

score: 0
Accepted
time: 110ms
memory: 70832kb

input:

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

output:

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

result:

ok correct!

Test #13:

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

input:

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

output:

50.0979452055
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: 36ms
memory: 69872kb

input:

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

output:

100.7112010796
742
(1,1) (2,1) 

result:

ok correct!

Test #15:

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

input:

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

output:

494.4978813559
1503
(56,38) (56,39) 

result:

ok correct!

Test #16:

score: 0
Accepted
time: 33ms
memory: 67648kb

input:

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

output:

122.5453116815
387
(1,19) (19,32) 

result:

ok correct!

Test #17:

score: 0
Accepted
time: 42ms
memory: 61328kb

input:

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

output:

103.4874441004
334
(10,57) (11,57) 

result:

ok correct!

Test #18:

score: 0
Accepted
time: 24ms
memory: 59392kb

input:

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

output:

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

result:

ok correct!

Test #19:

score: 0
Accepted
time: 41ms
memory: 67104kb

input:

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

output:

79.1493333333
319
(1,39) (1,40) 

result:

ok correct!

Test #20:

score: 0
Accepted
time: 57ms
memory: 69108kb

input:

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

output:

383.8083237877
1084
(93,9) (51,51) 

result:

ok correct!

Test #21:

score: 0
Accepted
time: 45ms
memory: 64204kb

input:

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

output:

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

result:

ok correct!

Test #22:

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

input:

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

output:

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

result:

ok correct!

Test #23:

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

input:

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

output:

291.7060294526
860
(1,1) (1,50) 

result:

ok correct!

Test #24:

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

input:

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

output:

152.1618806306
512
(48,9) (48,67) 

result:

ok correct!

Test #25:

score: 0
Accepted
time: 116ms
memory: 98536kb

input:

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

output:

212.3962500000
1031
(1,67) (1,68) 

result:

ok correct!

Test #26:

score: 0
Accepted
time: 58ms
memory: 75376kb

input:

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

output:

357.1213272543
2687
(1,83) (1,84) 

result:

ok correct!

Test #27:

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

input:

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

output:

225.8555232558
975
(84,1) (85,1) 

result:

ok correct!

Test #28:

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

input:

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

output:

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

result:

ok correct!

Test #29:

score: 0
Accepted
time: 59ms
memory: 66976kb

input:

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

output:

738.9744796380
3378
(5,45) (5,56) 

result:

ok correct!

Test #30:

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

input:

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

output:

1550.3909774436
4192
(76,34) (76,96) 

result:

ok correct!

Test #31:

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

input:

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

output:

648.6502166586
2420
(16,1) (1,13) 

result:

ok correct!

Test #32:

score: 0
Accepted
time: 58ms
memory: 71648kb

input:

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

output:

207.3377551020
895
(1,97) (1,98) 

result:

ok correct!

Test #33:

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

input:

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

output:

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

result:

ok correct!

Test #34:

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

input:

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

output:

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

result:

ok correct!

Test #35:

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

input:

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

output:

142.1538240368
673
(1,74) (2,74) 

result:

ok correct!

Test #36:

score: 0
Accepted
time: 41ms
memory: 66168kb

input:

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

output:

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

result:

ok correct!

Test #37:

score: 0
Accepted
time: 44ms
memory: 66780kb

input:

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

output:

81.6699849170
314
(1,64) (1,65) 

result:

ok correct!

Test #38:

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

input:

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

output:

300.3075268817
1326
(39,93) (40,93) 

result:

ok correct!

Test #39:

score: 0
Accepted
time: 58ms
memory: 80752kb

input:

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

output:

474.0689655172
2063
(1,1) (49,1) 

result:

ok correct!

Test #40:

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

input:

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

output:

2555.3674838113
5914
(46,1) (46,2) 

result:

ok correct!

Test #41:

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

input:

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

output:

2389.2003584229
11288
(21,60) (22,60) 

result:

ok correct!

Test #42:

score: 0
Accepted
time: 41ms
memory: 73220kb

input:

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

output:

225.0891602543
803
(10,61) (11,61) 

result:

ok correct!

Test #43:

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

input:

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

output:

213.6875699888
941
(33,89) (33,90) 

result:

ok correct!

Test #44:

score: 0
Accepted
time: 56ms
memory: 70188kb

input:

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

output:

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

result:

ok correct!

Test #45:

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

input:

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

output:

67.3547430830
645
(1,1) (2,1) 

result:

ok correct!

Test #46:

score: 0
Accepted
time: 47ms
memory: 69692kb

input:

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

output:

80.0410256410
332
(64,34) (65,34) 

result:

ok correct!

Test #47:

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

input:

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

output:

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

result:

ok correct!

Test #48:

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

input:

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

output:

302.7898467433
799
(87,29) (87,58) 

result:

ok correct!

Test #49:

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

input:

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

output:

150.3469125214
930
(52,44) (53,44) 

result:

ok correct!

Test #50:

score: 0
Accepted
time: 53ms
memory: 75932kb

input:

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

output:

690.6464136872
3826
(1,96) (1,97) 

result:

ok correct!

Test #51:

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

input:

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

output:

356.9745798319
1620
(23,68) (51,68) 

result:

ok correct!

Test #52:

score: 0
Accepted
time: 28ms
memory: 61448kb

input:

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

output:

1705.1021978022
4664
(100,44) (100,90) 

result:

ok correct!

Test #53:

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

input:

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

output:

2976.1423160173
8305
(68,1) (69,1) 

result:

ok correct!

Test #54:

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

input:

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

output:

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

result:

ok correct!

Test #55:

score: 0
Accepted
time: 64ms
memory: 79820kb

input:

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

output:

179.2792517007
713
(98,56) (98,57) 

result:

ok correct!

Test #56:

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

input:

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

output:

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

result:

ok correct!

Test #57:

score: 0
Accepted
time: 42ms
memory: 75012kb

input:

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

output:

115.9405701754
390
(15,48) (79,48) 

result:

ok correct!

Test #58:

score: 0
Accepted
time: 32ms
memory: 61660kb

input:

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

output:

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

result:

ok correct!

Test #59:

score: 0
Accepted
time: 95ms
memory: 90028kb

input:

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

output:

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

result:

ok correct!

Test #60:

score: 0
Accepted
time: 58ms
memory: 77380kb

input:

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

output:

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

result:

ok correct!

Test #61:

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

input:

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

output:

164.8780780781
772
(1,7) (1,8) 

result:

ok correct!

Test #62:

score: 0
Accepted
time: 52ms
memory: 69648kb

input:

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

output:

106.0129375951
560
(1,1) (1,2) 

result:

ok correct!

Test #63:

score: 0
Accepted
time: 53ms
memory: 74672kb

input:

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

output:

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

result:

ok correct!

Test #64:

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

input:

1 2
X
X

output:

1.0000000000
1
(1,1) (1,2) 

result:

ok correct!

Test #65:

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

input:

1 3
X
.
.

output:

0.6666666667
1
(1,1) (1,2) 

result:

ok correct!

Test #66:

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

input:

1 3
.
X
.

output:

0.6666666667
1
(1,1) (1,3) 

result:

ok correct!

Test #67:

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

input:

1 3
X
X
.

output:

0.6666666667
1
(1,2) (1,3) 

result:

ok correct!

Test #68:

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

input:

1 3
.
.
X

output:

3.3333333333
5
(1,2) (1,3) 

result:

ok correct!

Test #69:

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

input:

1 3
X
.
X

output:

6.6666666667
10
(1,1) (1,3) 

result:

ok correct!

Test #70:

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

input:

1 3
.
X
X

output:

0.6666666667
1
(1,1) (1,2) 

result:

ok correct!

Test #71:

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

input:

1 3
X
X
X

output:

3.6666666667
5
(1,1) (1,2) 

result:

ok correct!

Test #72:

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

input:

1 4
X
.
.
.

output:

5.2500000000
10
(1,1) (1,2) 

result:

ok correct!

Test #73:

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

input:

1 4
.
X
.
.

output:

2.7500000000
5
(1,1) (1,4) 

result:

ok correct!

Test #74:

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

input:

1 4
X
X
.
.

output:

1.0000000000
1
(1,1) (1,2) (1,3) (1,4) 

result:

ok correct!

Test #75:

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

input:

1 4
.
.
X
.

output:

2.7500000000
5
(1,3) (1,4) 

result:

ok correct!

Test #76:

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

input:

1 4
X
.
X
.

output:

7.5000000000
10
(1,2) (1,4) 

result:

ok correct!

Test #77:

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

input:

1 4
.
X
X
.

output:

1.0000000000
1
(1,1) (1,2) (1,3) (1,4) 

result:

ok correct!

Test #78:

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

input:

1 4
X
X
X
.

output:

2.7500000000
5
(1,2) (1,3) 

result:

ok correct!

Test #79:

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

input:

1 4
.
.
.
X

output:

10.2500000000
18
(1,3) (1,4) 

result:

ok correct!

Test #80:

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

input:

1 4
X
.
.
X

output:

14.0000000000
27
(1,1) (1,4) 

result:

ok correct!

Test #81:

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

input:

1 4
.
X
.
X

output:

5.5000000000
10
(1,1) (1,3) 

result:

ok correct!

Test #82:

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

input:

1 4
X
X
.
X

output:

2.7500000000
5
(1,1) (1,4) 

result:

ok correct!

Test #83:

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

input:

1 4
.
.
X
X

output:

3.0000000000
5
(1,3) (1,4) 

result:

ok correct!

Test #84:

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

input:

1 4
X
.
X
X

output:

2.7500000000
5
(1,2) (1,4) 

result:

ok correct!

Test #85:

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

input:

1 4
.
X
X
X

output:

2.7500000000
5
(1,1) (1,2) 

result:

ok correct!

Test #86:

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

input:

1 4
X
X
X
X

output:

6.5000000000
10
(1,2) (1,3) 

result:

ok correct!

Test #87:

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

input:

2 2
X.
..

output:

3.7500000000
7
(2,1) (2,2) 

result:

ok correct!

Test #88:

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

input:

2 2
.X
..

output:

1.2500000000
2
(1,1) (1,2) 

result:

ok correct!

Test #89:

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

input:

2 2
XX
..

output:

2.5000000000
3
(1,2) (2,2) 

result:

ok correct!

Test #90:

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

input:

2 2
..
X.

output:

4.2500000000
6
(2,1) (2,2) 

result:

ok correct!

Test #91:

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

input:

2 2
X.
X.

output:

3.5000000000
6
(2,1) (2,2) 

result:

ok correct!

Test #92:

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

input:

2 2
.X
X.

output:

1.5000000000
2
(1,1) (2,2) 

result:

ok correct!

Test #93:

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

input:

2 2
XX
X.

output:

1.7500000000
3
(1,2) (2,2) 

result:

ok correct!

Test #94:

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

input:

2 2
..
.X

output:

2.7500000000
4
(1,2) (2,2) 

result:

ok correct!

Test #95:

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

input:

2 2
X.
.X

output:

2.5000000000
4
(2,1) (1,2) 

result:

ok correct!

Test #96:

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

input:

2 2
.X
.X

output:

1.5000000000
2
(1,1) (1,2) 

result:

ok correct!

Test #97:

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

input:

2 2
XX
.X

output:

1.7500000000
3
(1,2) (2,2) 

result:

ok correct!

Test #98:

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

input:

2 2
..
XX

output:

3.5000000000
4
(1,2) (2,2) 

result:

ok correct!

Test #99:

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

input:

2 2
X.
XX

output:

2.2500000000
4
(2,1) (1,2) 

result:

ok correct!

Test #100:

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

input:

2 2
.X
XX

output:

1.2500000000
2
(1,1) (2,2) 

result:

ok correct!

Test #101:

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

input:

2 2
XX
XX

output:

2.5000000000
3
(1,2) (2,2) 

result:

ok correct!

Test #102:

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

input:

3 1
X..

output:

4.6666666667
7
(2,1) (3,1) 

result:

ok correct!

Test #103:

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

input:

3 1
.X.

output:

2.0000000000
3
(1,1) (3,1) 

result:

ok correct!

Test #104:

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

input:

3 1
XX.

output:

2.0000000000
3
(1,1) (2,1) 

result:

ok correct!

Test #105:

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

input:

3 1
..X

output:

2.0000000000
3
(1,1) (2,1) 

result:

ok correct!

Test #106:

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

input:

3 1
X.X

output:

9.3333333333
14
(1,1) (3,1) 

result:

ok correct!

Test #107:

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

input:

3 1
.XX

output:

2.0000000000
3
(2,1) (3,1) 

result:

ok correct!

Test #108:

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

input:

3 1
XXX

output:

5.6666666667
7
(1,1) (2,1) 

result:

ok correct!

Test #109:

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

input:

4 1
X...

output:

12.7500000000
22
(3,1) (4,1) 

result:

ok correct!

Test #110:

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

input:

4 1
.X..

output:

4.2500000000
7
(3,1) (4,1) 

result:

ok correct!

Test #111:

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

input:

4 1
XX..

output:

5.0000000000
7
(3,1) (4,1) 

result:

ok correct!

Test #112:

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

input:

4 1
..X.

output:

4.2500000000
7
(1,1) (4,1) 

result:

ok correct!

Test #113:

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

input:

4 1
X.X.

output:

8.5000000000
14
(1,1) (3,1) 

result:

ok correct!

Test #114:

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

input:

4 1
.XX.

output:

3.0000000000
3
(1,1) (2,1) (3,1) (4,1) 

result:

ok correct!

Test #115:

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

input:

4 1
XXX.

output:

4.2500000000
7
(1,1) (2,1) 

result:

ok correct!

Test #116:

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

input:

4 1
...X

output:

7.7500000000
14
(1,1) (2,1) 

result:

ok correct!

Test #117:

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

input:

4 1
X..X

output:

18.0000000000
33
(1,1) (4,1) 

result:

ok correct!

Test #118:

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

input:

4 1
.X.X

output:

10.5000000000
14
(2,1) (4,1) 

result:

ok correct!

Test #119:

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

input:

4 1
XX.X

output:

4.2500000000
7
(2,1) (4,1) 

result:

ok correct!

Test #120:

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

input:

4 1
..XX

output:

3.0000000000
3
(1,1) (2,1) (3,1) (4,1) 

result:

ok correct!

Test #121:

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

input:

4 1
X.XX

output:

4.2500000000
7
(1,1) (4,1) 

result:

ok correct!

Test #122:

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

input:

4 1
.XXX

output:

4.2500000000
7
(2,1) (3,1) 

result:

ok correct!

Test #123:

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

input:

4 1
XXXX

output:

9.5000000000
14
(2,1) (3,1) 

result:

ok correct!

Test #124:

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

input:

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

output:

13274.5900000000
38710
(99,1) (100,1) 

result:

ok correct!

Test #125:

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

input:

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

output:

13076.6300000000
38318
(1,1) (2,1) 

result:

ok correct!

Test #126:

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

input:

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

output:

3356.0100000000
9751
(1,1) (100,1) 

result:

ok correct!

Test #127:

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

input:

100 1
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

output:

3457.5000000000
9950
(50,1) (51,1) 

result:

ok correct!

Test #128:

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

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

result:

ok correct!

Test #129:

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

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

result:

ok correct!

Test #130:

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

input:

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

output:

12977.6500000000
38122
(1,1) (1,2) 

result:

ok correct!

Test #131:

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

input:

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

output:

13175.6100000000
38514
(1,99) (1,100) 

result:

ok correct!

Test #132:

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

input:

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

output:

3306.0300000000
9653
(1,99) (1,100) 

result:

ok correct!

Test #133:

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

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

result:

ok correct!

Test #134:

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

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

result:

ok correct!

Test #135:

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

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

result:

ok correct!

Test #136:

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

input:

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

output:

58.0800000000
95
(5,10) (6,10) 

result:

ok correct!

Test #137:

score: 0
Accepted
time: 81ms
memory: 85556kb

input:

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

output:

13878.9275000000
38908
(99,1) (100,1) 

result:

ok correct!

Test #138:

score: 0
Accepted
time: 77ms
memory: 85932kb

input:

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

output:

14059.2725000000
39302
(99,100) (100,100) 

result:

ok correct!

Test #139:

score: 0
Accepted
time: 102ms
memory: 85924kb

input:

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

output:

14132.2825000000
39500
(100,1) (100,2) 

result:

ok correct!

Test #140:

score: 0
Accepted
time: 92ms
memory: 85744kb

input:

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

output:

13951.4325000000
39104
(1,99) (1,100) 

result:

ok correct!

Test #141:

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

input:

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

output:

19733.3399000000
39302
(99,100) (100,100) 

result:

ok correct!

Test #142:

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

input:

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

output:

19601.0099000000
39104
(1,99) (1,100) 

result:

ok correct!

Test #143:

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

input:

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

output:

5001.4899000000
10098
(99,100) (100,100) 

result:

ok correct!

Test #144:

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

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

result:

ok correct!

Test #145:

score: 0
Accepted
time: 36ms
memory: 65908kb

input:

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

output:

60.8308000000
195
(28,1) (1,35) 

result:

ok correct!

Test #146:

score: 0
Accepted
time: 117ms
memory: 100716kb

input:

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

output:

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

result:

ok correct!

Extra Test:

score: 0
Extra Test Passed