QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#386742#5112. Where Am I?PetroTarnavskyi#AC ✓179ms18224kbC++202.3kb2024-04-11 19:47:402024-04-11 19:47:41

Judging History

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

  • [2024-04-11 19:47:41]
  • 评测
  • 测评结果:AC
  • 用时:179ms
  • 内存:18224kb
  • [2024-04-11 19:47:40]
  • 提交

answer

#include <bits/stdc++.h> 

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

map<PII, int> mp;

void precalc()
{
	mp[{0, 0}] = 0;
	int x = 0, y = 0;
	int id = 1;
	FOR(i, 0, 200)
	{
		FOR(j, 0, 2 * i + 1)
		{
			y++;
			mp[{x, y}] = id++;
		}
		FOR(j, 0, 2 * i + 1)
		{
			x++;
			mp[{x, y}] = id++;
		}
		FOR(j, 0, 2 * i + 2)
		{
			y--;
			mp[{x, y}] = id++;
		}
		FOR(j, 0, 2 * i + 2)
		{
			x--;
			mp[{x, y}] = id++;
		}
	}
}

int f(const VI& a, const VI& b)
{
	assert(SZ(a) == SZ(b));
	int ptr = 0;
	while (ptr < SZ(a) && a[ptr] == b[ptr])
		ptr++;
	assert(ptr < SZ(a) && a[ptr] < b[ptr]);
	return a[ptr];
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int n, m;
	cin >> m >> n;
	vector<string> s(n);
	for (string& si : s)
		cin >> si;
	reverse(ALL(s));
	precalc();
	FOR(i, -100, 101)
		FOR(j, -100, 101)
			assert(mp.count({i, j}));
	cerr << (db)clock() / CLOCKS_PER_SEC << endl;
	vector<PII> crosses;
	FOR(i, 0, n)
		FOR(j, 0, m)
			if (s[i][j] == 'X')
				crosses.PB({i, j});
	vector<tuple<VI, int, int>> vec;
	vec.reserve(n * m);
	VI cur;
	FOR(i, 0, n)
	{
		FOR(j, 0, m)
		{
			cur.clear();
			for (auto [ycr, xcr] : crosses)
			{
				cur.PB(mp[{xcr - j, ycr - i}]);
			}
			sort(ALL(cur));
			vec.PB({cur, i, j});
		}
	}
	sort(ALL(vec));
	LL sum = 0, mx = 0;
	vector<PII> vecMx;
	assert(SZ(vec) == n * m);
	FOR(i, 0, SZ(vec))
	{
		const auto& [curVec, y, x] = vec[i];
		int difLeft = i == 0 ? 0 : f(get<0>(vec[i - 1]), curVec);
		int difRight = i + 1 == SZ(vec) ? 0 : f(curVec, get<0>(vec[i + 1]));
		int steps = max(difLeft, difRight);
		sum += steps;
		if (steps > mx)
		{
			mx = steps;
			vecMx.clear();
		}
		if (steps == mx)
		{
			vecMx.PB({y, x});
		}
	}
	sort(ALL(vecMx));
	cout << (db)sum / (n * m) << "\n";
	cout << mx << "\n";
	FOR(i, 0, SZ(vecMx))
	{
		auto [y, x] = vecMx[i];
		if (i)
			cout << " ";
		cout << "(" << x + 1 << "," << y + 1 << ")";
	}
	cout << "\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 27ms
memory: 14016kb

input:

1 1
X

output:

0.0000000000
0
(1,1)

result:

ok correct!

Test #2:

score: 0
Accepted
time: 30ms
memory: 14180kb

input:

2 1
.X

output:

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

result:

ok correct!

Test #3:

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

input:

2 1
X.

output:

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

result:

ok correct!

Test #4:

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

input:

1 2
.
X

output:

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

result:

ok correct!

Test #5:

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

input:

1 2
X
.

output:

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

result:

ok correct!

Test #6:

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

input:

2 1
XX

output:

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

result:

ok correct!

Test #7:

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

input:

3 3
XXX
X.X
XXX

output:

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

result:

ok correct!

Test #8:

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

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

input:

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

output:

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

result:

ok correct!

Test #10:

score: 0
Accepted
time: 34ms
memory: 14304kb

input:

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

output:

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

result:

ok correct!

Test #11:

score: 0
Accepted
time: 153ms
memory: 18068kb

input:

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

output:

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

result:

ok correct!

Test #12:

score: 0
Accepted
time: 139ms
memory: 18136kb

input:

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

output:

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

result:

ok correct!

Test #13:

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

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

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

input:

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

output:

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

result:

ok correct!

Test #16:

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

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

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

input:

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

output:

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

result:

ok correct!

Test #19:

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

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

input:

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

output:

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

result:

ok correct!

Test #21:

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

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

input:

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

output:

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

result:

ok correct!

Test #23:

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

input:

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

output:

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

result:

ok correct!

Test #24:

score: 0
Accepted
time: 50ms
memory: 14848kb

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

input:

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

output:

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

result:

ok correct!

Test #26:

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

input:

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

output:

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

result:

ok correct!

Test #27:

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

input:

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

output:

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

result:

ok correct!

Test #28:

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

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

input:

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

output:

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

result:

ok correct!

Test #30:

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

input:

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

output:

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

result:

ok correct!

Test #31:

score: 0
Accepted
time: 39ms
memory: 14512kb

input:

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

output:

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

result:

ok correct!

Test #32:

score: 0
Accepted
time: 67ms
memory: 15444kb

input:

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

output:

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

result:

ok correct!

Test #33:

score: 0
Accepted
time: 128ms
memory: 16784kb

input:

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

output:

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

result:

ok correct!

Test #34:

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

input:

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

output:

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

result:

ok correct!

Test #35:

score: 0
Accepted
time: 51ms
memory: 14796kb

input:

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

output:

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

result:

ok correct!

Test #36:

score: 0
Accepted
time: 50ms
memory: 15108kb

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

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

input:

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

output:

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

result:

ok correct!

Test #39:

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

input:

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

output:

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

result:

ok correct!

Test #40:

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

input:

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

output:

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

result:

ok correct!

Test #41:

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

input:

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

output:

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

result:

ok correct!

Test #42:

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

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

input:

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

output:

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

result:

ok correct!

Test #44:

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

input:

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

output:

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

result:

ok correct!

Test #45:

score: 0
Accepted
time: 51ms
memory: 14808kb

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

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

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

input:

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

output:

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

result:

ok correct!

Test #49:

score: 0
Accepted
time: 38ms
memory: 14348kb

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

input:

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

output:

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

result:

ok correct!

Test #51:

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

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

input:

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

output:

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

result:

ok correct!

Test #53:

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

input:

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

output:

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

result:

ok correct!

Test #54:

score: 0
Accepted
time: 39ms
memory: 14364kb

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

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

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

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

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

input:

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

output:

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

result:

ok correct!

Test #60:

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

input:

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

output:

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

result:

ok correct!

Test #61:

score: 0
Accepted
time: 50ms
memory: 14832kb

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

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

input:

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

output:

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

result:

ok correct!

Test #64:

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

input:

1 2
X
X

output:

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

result:

ok correct!

Test #65:

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

input:

1 3
X
.
.

output:

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

result:

ok correct!

Test #66:

score: 0
Accepted
time: 30ms
memory: 14020kb

input:

1 3
.
X
.

output:

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

result:

ok correct!

Test #67:

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

input:

1 3
X
X
.

output:

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

result:

ok correct!

Test #68:

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

input:

1 3
.
.
X

output:

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

result:

ok correct!

Test #69:

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

input:

1 3
X
.
X

output:

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

result:

ok correct!

Test #70:

score: 0
Accepted
time: 30ms
memory: 13968kb

input:

1 3
.
X
X

output:

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

result:

ok correct!

Test #71:

score: 0
Accepted
time: 30ms
memory: 14016kb

input:

1 3
X
X
X

output:

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

result:

ok correct!

Test #72:

score: 0
Accepted
time: 30ms
memory: 14088kb

input:

1 4
X
.
.
.

output:

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

result:

ok correct!

Test #73:

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

input:

1 4
.
X
.
.

output:

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

result:

ok correct!

Test #74:

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

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

input:

1 4
.
.
X
.

output:

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

result:

ok correct!

Test #76:

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

input:

1 4
X
.
X
.

output:

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

result:

ok correct!

Test #77:

score: 0
Accepted
time: 30ms
memory: 14008kb

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

input:

1 4
X
X
X
.

output:

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

result:

ok correct!

Test #79:

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

input:

1 4
.
.
.
X

output:

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

result:

ok correct!

Test #80:

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

input:

1 4
X
.
.
X

output:

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

result:

ok correct!

Test #81:

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

input:

1 4
.
X
.
X

output:

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

result:

ok correct!

Test #82:

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

input:

1 4
X
X
.
X

output:

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

result:

ok correct!

Test #83:

score: 0
Accepted
time: 30ms
memory: 14012kb

input:

1 4
.
.
X
X

output:

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

result:

ok correct!

Test #84:

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

input:

1 4
X
.
X
X

output:

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

result:

ok correct!

Test #85:

score: 0
Accepted
time: 30ms
memory: 14112kb

input:

1 4
.
X
X
X

output:

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

result:

ok correct!

Test #86:

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

input:

1 4
X
X
X
X

output:

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

result:

ok correct!

Test #87:

score: 0
Accepted
time: 30ms
memory: 14116kb

input:

2 2
X.
..

output:

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

result:

ok correct!

Test #88:

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

input:

2 2
.X
..

output:

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

result:

ok correct!

Test #89:

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

input:

2 2
XX
..

output:

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

result:

ok correct!

Test #90:

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

input:

2 2
..
X.

output:

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

result:

ok correct!

Test #91:

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

input:

2 2
X.
X.

output:

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

result:

ok correct!

Test #92:

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

input:

2 2
.X
X.

output:

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

result:

ok correct!

Test #93:

score: 0
Accepted
time: 30ms
memory: 14116kb

input:

2 2
XX
X.

output:

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

result:

ok correct!

Test #94:

score: 0
Accepted
time: 30ms
memory: 14176kb

input:

2 2
..
.X

output:

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

result:

ok correct!

Test #95:

score: 0
Accepted
time: 30ms
memory: 13944kb

input:

2 2
X.
.X

output:

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

result:

ok correct!

Test #96:

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

input:

2 2
.X
.X

output:

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

result:

ok correct!

Test #97:

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

input:

2 2
XX
.X

output:

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

result:

ok correct!

Test #98:

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

input:

2 2
..
XX

output:

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

result:

ok correct!

Test #99:

score: 0
Accepted
time: 30ms
memory: 13904kb

input:

2 2
X.
XX

output:

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

result:

ok correct!

Test #100:

score: 0
Accepted
time: 30ms
memory: 13944kb

input:

2 2
.X
XX

output:

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

result:

ok correct!

Test #101:

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

input:

2 2
XX
XX

output:

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

result:

ok correct!

Test #102:

score: 0
Accepted
time: 30ms
memory: 14004kb

input:

3 1
X..

output:

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

result:

ok correct!

Test #103:

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

input:

3 1
.X.

output:

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

result:

ok correct!

Test #104:

score: 0
Accepted
time: 30ms
memory: 14172kb

input:

3 1
XX.

output:

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

result:

ok correct!

Test #105:

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

input:

3 1
..X

output:

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

result:

ok correct!

Test #106:

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

input:

3 1
X.X

output:

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

result:

ok correct!

Test #107:

score: 0
Accepted
time: 30ms
memory: 14008kb

input:

3 1
.XX

output:

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

result:

ok correct!

Test #108:

score: 0
Accepted
time: 30ms
memory: 14180kb

input:

3 1
XXX

output:

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

result:

ok correct!

Test #109:

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

input:

4 1
X...

output:

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

result:

ok correct!

Test #110:

score: 0
Accepted
time: 30ms
memory: 14000kb

input:

4 1
.X..

output:

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

result:

ok correct!

Test #111:

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

input:

4 1
XX..

output:

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

result:

ok correct!

Test #112:

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

input:

4 1
..X.

output:

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

result:

ok correct!

Test #113:

score: 0
Accepted
time: 30ms
memory: 14044kb

input:

4 1
X.X.

output:

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

result:

ok correct!

Test #114:

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

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

input:

4 1
XXX.

output:

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

result:

ok correct!

Test #116:

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

input:

4 1
...X

output:

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

result:

ok correct!

Test #117:

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

input:

4 1
X..X

output:

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

result:

ok correct!

Test #118:

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

input:

4 1
.X.X

output:

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

result:

ok correct!

Test #119:

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

input:

4 1
XX.X

output:

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

result:

ok correct!

Test #120:

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

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

input:

4 1
X.XX

output:

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

result:

ok correct!

Test #122:

score: 0
Accepted
time: 30ms
memory: 14080kb

input:

4 1
.XXX

output:

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

result:

ok correct!

Test #123:

score: 0
Accepted
time: 30ms
memory: 14016kb

input:

4 1
XXXX

output:

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

result:

ok correct!

Test #124:

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

input:

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

output:

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

result:

ok correct!

Test #125:

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

input:

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

output:

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

result:

ok correct!

Test #126:

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

input:

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

output:

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

result:

ok correct!

Test #127:

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

input:

100 1
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

output:

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

result:

ok correct!

Test #128:

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

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

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

input:

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

output:

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

result:

ok correct!

Test #131:

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

input:

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

output:

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

result:

ok correct!

Test #132:

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

input:

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

output:

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

result:

ok correct!

Test #133:

score: 0
Accepted
time: 30ms
memory: 14048kb

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

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

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

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

input:

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

output:

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

result:

ok correct!

Test #138:

score: 0
Accepted
time: 78ms
memory: 18044kb

input:

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

output:

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

result:

ok correct!

Test #139:

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

input:

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

output:

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

result:

ok correct!

Test #140:

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

input:

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

output:

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

result:

ok correct!

Test #141:

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

input:

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

output:

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

result:

ok correct!

Test #142:

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

input:

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

output:

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

result:

ok correct!

Test #143:

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

input:

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

output:

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

result:

ok correct!

Test #144:

score: 0
Accepted
time: 34ms
memory: 14076kb

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

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

input:

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

output:

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

result:

ok correct!

Extra Test:

score: 0
Extra Test Passed