QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#387317#5112. Where Am I?ucup-team1209#AC ✓866ms1686992kbC++202.4kb2024-04-12 13:15:112024-04-12 13:15:11

Judging History

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

  • [2024-04-12 13:15:11]
  • 评测
  • 测评结果:AC
  • 用时:866ms
  • 内存:1686992kb
  • [2024-04-12 13:15:11]
  • 提交

answer

#include <bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
using ll = long long ; 
using pi = pair <int, int> ; 
cs int N = 105 + 5; 

void cmx(ll & x, ll y) {
    if(x < y) x = y; 
}

int n, m; 
char mp[N][N];
int ans[N][N];


int Map(int x, int y) {
    if(x <= 0 || y <= 0 || x > n || y > m) return 0; 
    return mp[x][y] == 'X';
}
pi direction(int d) {
    if(d == 0) return {-1, 0};
    int m = sqrt(d);
    if(m % 2 == 0) -- m; 
    if(d < m * m + m) {
        return {0, 1};
    }
    if(d < (m + 1) * (m + 1)) {
        return {1, 0};
    }
    if(d < (m + 1) * (m + 2)) {
        return {0, -1};
    }
    return {-1, 0};
}
void dfs(vector <pi> & S, int d, int dx, int dy) {
    if(S.empty()) return;
    if(S.size() == 1) {
        auto [x, y] = S[0];
        ans[x - dx][y - dy] = max(0, d - 1); 
        return; 
    }
    vector <pi> T[2];
    auto [cx, cy] = direction(d);
    for(auto [x, y] : S) {
        // cout << x << ' ' << y << ' ' << Map(x, y) << endl;
        T[Map(x, y)].pb({x + cx, y + cy});
    }
    // cout << d << ' ' << dx <<' ' << dy << endl;
    // for(auto [x, y] :S) cout << x << ' ' << y <<' '; cout << endl;
    // static int t = 0;
    // if(++ t == 50) exit(0);
    dfs(T[0], d + 1, dx + cx, dy + cy);
    dfs(T[1], d + 1, dx + cx, dy + cy);
}

int main() {
    #ifdef zqj
    freopen("1.in","r",stdin);
    #endif
    // ios :: sync_with_stdio(0), cin.tie(0);
    cin >> m >> n; 
    vector <pi> S; 
    for(int i = 1; i <= n; i++) {
        scanf("%s", mp[i] + 1);
        for(int j = 1; j <= m; j++) {
            S.pb({i, j});
        }
    }
    dfs(S, 0, 0, 0);
    int sum = 0, mx = 0; 
    vector <pi> t; 
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            sum += ans[i][j];
            if(ans[i][j] > mx) {
                t = {{n - i + 1, j}};
                mx = ans[i][j];
            }
            else if(ans[i][j] == mx) {
                t.pb({n - i + 1, j});
            }
        }
    }
    // cout << "FFFFF " << sum << ' ' << mx << endl;
    sort(t.begin(), t.end());
    printf("%.10lf\n", 1.0 * sum / (n * m)); 
    cout << mx << '\n';
    for(int i = 0; i < t.size(); i++) {
        auto [x, y] = t[i];
        cout << "(" << y << "," << x << ")";  
        if(i + 1 < t.size()) cout << ' ';
    }
    cout << '\n';
    return 0; 
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 1
X

output:

0.0000000000
0
(1,1)

result:

ok correct!

Test #2:

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

input:

2 1
.X

output:

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

result:

ok correct!

Test #3:

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

input:

2 1
X.

output:

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

result:

ok correct!

Test #4:

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

input:

1 2
.
X

output:

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

result:

ok correct!

Test #5:

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

input:

1 2
X
.

output:

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

result:

ok correct!

Test #6:

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

input:

2 1
XX

output:

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

result:

ok correct!

Test #7:

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

input:

3 3
XXX
X.X
XXX

output:

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

result:

ok correct!

Test #8:

score: 0
Accepted
time: 617ms
memory: 149268kb

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

input:

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

output:

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

result:

ok correct!

Test #10:

score: 0
Accepted
time: 656ms
memory: 1686992kb

input:

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

output:

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

result:

ok correct!

Test #11:

score: 0
Accepted
time: 866ms
memory: 169628kb

input:

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

output:

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

result:

ok correct!

Test #12:

score: 0
Accepted
time: 829ms
memory: 169016kb

input:

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

output:

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

result:

ok correct!

Test #13:

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

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

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

input:

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

output:

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

result:

ok correct!

Test #16:

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

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

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

input:

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

output:

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

result:

ok correct!

Test #19:

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

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

input:

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

output:

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

result:

ok correct!

Test #21:

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

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

input:

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

output:

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

result:

ok correct!

Test #23:

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

input:

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

output:

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

result:

ok correct!

Test #24:

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

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

input:

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

output:

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

result:

ok correct!

Test #26:

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

input:

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

output:

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

result:

ok correct!

Test #27:

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

input:

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

output:

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

result:

ok correct!

Test #28:

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

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

input:

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

output:

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

result:

ok correct!

Test #30:

score: 0
Accepted
time: 155ms
memory: 72412kb

input:

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

output:

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

result:

ok correct!

Test #31:

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

input:

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

output:

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

result:

ok correct!

Test #32:

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

input:

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

output:

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

result:

ok correct!

Test #33:

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

input:

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

output:

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

result:

ok correct!

Test #34:

score: 0
Accepted
time: 195ms
memory: 33960kb

input:

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

output:

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

result:

ok correct!

Test #35:

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

input:

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

output:

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

result:

ok correct!

Test #36:

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

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

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

input:

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

output:

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

result:

ok correct!

Test #39:

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

input:

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

output:

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

result:

ok correct!

Test #40:

score: 0
Accepted
time: 205ms
memory: 56076kb

input:

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

output:

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

result:

ok correct!

Test #41:

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

input:

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

output:

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

result:

ok correct!

Test #42:

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

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

input:

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

output:

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

result:

ok correct!

Test #44:

score: 0
Accepted
time: 222ms
memory: 12200kb

input:

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

output:

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

result:

ok correct!

Test #45:

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

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

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

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

input:

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

output:

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

result:

ok correct!

Test #49:

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

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

input:

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

output:

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

result:

ok correct!

Test #51:

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

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

input:

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

output:

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

result:

ok correct!

Test #53:

score: 0
Accepted
time: 288ms
memory: 134868kb

input:

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

output:

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

result:

ok correct!

Test #54:

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

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

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

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

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

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

input:

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

output:

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

result:

ok correct!

Test #60:

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

input:

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

output:

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

result:

ok correct!

Test #61:

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

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

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

input:

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

output:

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

result:

ok correct!

Test #64:

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

input:

1 2
X
X

output:

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

result:

ok correct!

Test #65:

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

input:

1 3
X
.
.

output:

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

result:

ok correct!

Test #66:

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

input:

1 3
.
X
.

output:

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

result:

ok correct!

Test #67:

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

input:

1 3
X
X
.

output:

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

result:

ok correct!

Test #68:

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

input:

1 3
.
.
X

output:

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

result:

ok correct!

Test #69:

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

input:

1 3
X
.
X

output:

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

result:

ok correct!

Test #70:

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

input:

1 3
.
X
X

output:

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

result:

ok correct!

Test #71:

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

input:

1 3
X
X
X

output:

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

result:

ok correct!

Test #72:

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

input:

1 4
X
.
.
.

output:

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

result:

ok correct!

Test #73:

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

input:

1 4
.
X
.
.

output:

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

result:

ok correct!

Test #74:

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

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

input:

1 4
.
.
X
.

output:

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

result:

ok correct!

Test #76:

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

input:

1 4
X
.
X
.

output:

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

result:

ok correct!

Test #77:

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

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

input:

1 4
X
X
X
.

output:

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

result:

ok correct!

Test #79:

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

input:

1 4
.
.
.
X

output:

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

result:

ok correct!

Test #80:

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

input:

1 4
X
.
.
X

output:

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

result:

ok correct!

Test #81:

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

input:

1 4
.
X
.
X

output:

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

result:

ok correct!

Test #82:

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

input:

1 4
X
X
.
X

output:

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

result:

ok correct!

Test #83:

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

input:

1 4
.
.
X
X

output:

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

result:

ok correct!

Test #84:

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

input:

1 4
X
.
X
X

output:

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

result:

ok correct!

Test #85:

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

input:

1 4
.
X
X
X

output:

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

result:

ok correct!

Test #86:

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

input:

1 4
X
X
X
X

output:

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

result:

ok correct!

Test #87:

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

input:

2 2
X.
..

output:

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

result:

ok correct!

Test #88:

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

input:

2 2
.X
..

output:

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

result:

ok correct!

Test #89:

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

input:

2 2
XX
..

output:

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

result:

ok correct!

Test #90:

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

input:

2 2
..
X.

output:

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

result:

ok correct!

Test #91:

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

input:

2 2
X.
X.

output:

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

result:

ok correct!

Test #92:

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

input:

2 2
.X
X.

output:

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

result:

ok correct!

Test #93:

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

input:

2 2
XX
X.

output:

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

result:

ok correct!

Test #94:

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

input:

2 2
..
.X

output:

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

result:

ok correct!

Test #95:

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

input:

2 2
X.
.X

output:

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

result:

ok correct!

Test #96:

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

input:

2 2
.X
.X

output:

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

result:

ok correct!

Test #97:

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

input:

2 2
XX
.X

output:

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

result:

ok correct!

Test #98:

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

input:

2 2
..
XX

output:

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

result:

ok correct!

Test #99:

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

input:

2 2
X.
XX

output:

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

result:

ok correct!

Test #100:

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

input:

2 2
.X
XX

output:

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

result:

ok correct!

Test #101:

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

input:

2 2
XX
XX

output:

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

result:

ok correct!

Test #102:

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

input:

3 1
X..

output:

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

result:

ok correct!

Test #103:

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

input:

3 1
.X.

output:

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

result:

ok correct!

Test #104:

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

input:

3 1
XX.

output:

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

result:

ok correct!

Test #105:

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

input:

3 1
..X

output:

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

result:

ok correct!

Test #106:

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

input:

3 1
X.X

output:

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

result:

ok correct!

Test #107:

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

input:

3 1
.XX

output:

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

result:

ok correct!

Test #108:

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

input:

3 1
XXX

output:

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

result:

ok correct!

Test #109:

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

input:

4 1
X...

output:

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

result:

ok correct!

Test #110:

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

input:

4 1
.X..

output:

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

result:

ok correct!

Test #111:

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

input:

4 1
XX..

output:

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

result:

ok correct!

Test #112:

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

input:

4 1
..X.

output:

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

result:

ok correct!

Test #113:

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

input:

4 1
X.X.

output:

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

result:

ok correct!

Test #114:

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

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

input:

4 1
XXX.

output:

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

result:

ok correct!

Test #116:

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

input:

4 1
...X

output:

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

result:

ok correct!

Test #117:

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

input:

4 1
X..X

output:

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

result:

ok correct!

Test #118:

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

input:

4 1
.X.X

output:

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

result:

ok correct!

Test #119:

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

input:

4 1
XX.X

output:

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

result:

ok correct!

Test #120:

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

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

input:

4 1
X.XX

output:

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

result:

ok correct!

Test #122:

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

input:

4 1
.XXX

output:

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

result:

ok correct!

Test #123:

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

input:

4 1
XXXX

output:

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

result:

ok correct!

Test #124:

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

input:

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

output:

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

result:

ok correct!

Test #125:

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

input:

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

output:

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

result:

ok correct!

Test #126:

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

input:

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

output:

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

result:

ok correct!

Test #127:

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

input:

100 1
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

output:

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

result:

ok correct!

Test #128:

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

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

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

input:

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

output:

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

result:

ok correct!

Test #131:

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

input:

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

output:

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

result:

ok correct!

Test #132:

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

input:

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

output:

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

result:

ok correct!

Test #133:

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

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

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

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

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

input:

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

output:

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

result:

ok correct!

Test #138:

score: 0
Accepted
time: 497ms
memory: 1160328kb

input:

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

output:

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

result:

ok correct!

Test #139:

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

input:

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

output:

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

result:

ok correct!

Test #140:

score: 0
Accepted
time: 529ms
memory: 1153400kb

input:

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

output:

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

result:

ok correct!

Test #141:

score: 0
Accepted
time: 671ms
memory: 1675856kb

input:

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

output:

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

result:

ok correct!

Test #142:

score: 0
Accepted
time: 680ms
memory: 1665660kb

input:

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

output:

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

result:

ok correct!

Test #143:

score: 0
Accepted
time: 172ms
memory: 427764kb

input:

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

output:

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

result:

ok correct!

Test #144:

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

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

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

input:

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

output:

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

result:

ok correct!

Extra Test:

score: 0
Extra Test Passed