QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#63977#5112. Where Am I?Noobie_99AC ✓701ms7812kbC++202.3kb2022-11-23 20:37:272022-11-23 20:37:29

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-23 20:37:29]
  • 评测
  • 测评结果:AC
  • 用时:701ms
  • 内存:7812kb
  • [2022-11-23 20:37:27]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define debug(x) cerr << "[" << __LINE__ << ' ' << #x << "]: " << (x) << endl

int main() {
    cin.tie(0)->sync_with_stdio(0);

    vector<int> dx(1), dy(1);
    {
        int x = 0, y = 0;
        int cur = 1;
        while (dx.size() < 205*205) {
            for (int i=0; i<cur; i++) x--, dx.push_back(x), dy.push_back(y);
            for (int i=0; i<cur; i++) y++, dx.push_back(x), dy.push_back(y);
            cur++;
            for (int i=0; i<cur; i++) x++, dx.push_back(x), dy.push_back(y);
            for (int i=0; i<cur; i++) y--, dx.push_back(x), dy.push_back(y);
            cur++;
        }
    }

    int mxx, mxy;
    cin >> mxy >> mxx;

    bool a[mxx][mxy];
    for (int i=0; i<mxx; i++) for (int j=0; j<mxy; j++) {
        char c;
        cin >> c;
        a[i][j] = c != '.';
    }

    vector<tuple<vector<int>, int, int>> duh;
    for (int i=0; i<mxx; i++) for (int j=0; j<mxy; j++) {
        vector<int> idk;
        for (int k=0; k<(int)dx.size(); k++) {
            int ti = i + dx[k], tj = j + dy[k];
            if (ti < 0 || ti >= mxx || tj < 0 || tj >= mxy || !a[ti][tj]) continue;
            idk.push_back(k);
        }
        duh.emplace_back(idk, i, j);
    }
    sort(duh.begin(), duh.end());

    vector<int> share(mxx*mxy+1);
    for (int i=1; i<mxx*mxy; i++) {
        int cur = 0;
        while (get<0>(duh[i-1])[cur] == get<0>(duh[i])[cur]) cur++;
        share[i] = min(get<0>(duh[i-1])[cur], get<0>(duh[i])[cur]);
    }

    int mx = -1;
    vector<pair<int, int>> ans;
    ll sm = 0;
    for (int i=0; i<mxx*mxy; i++) {
        int cur = max(share[i], share[i+1]);
        if (cur > mx) {
            mx = cur;
            ans = {{get<2>(duh[i])+1, mxx-get<1>(duh[i])}};
        } else if (cur == mx) {
            ans.emplace_back(get<2>(duh[i])+1, mxx-get<1>(duh[i]));
        }
        sm += cur;
    }
    sort(ans.begin(), ans.end(), [](auto& x, auto& y) {
        if (x.second != y.second) return x.second < y.second;
        return x.first < y.first;
    });

    cout << setprecision(10) << fixed << sm / (double)(mxx*mxy) << '\n';
    cout << mx << '\n';
    for (auto [x, y] : ans) cout << "(" << x << "," << y << ") ";
    cout << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3736kb

input:

1 1
X

output:

0.0000000000
0
(1,1) 

result:

ok correct!

Test #2:

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

input:

2 1
.X

output:

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

result:

ok correct!

Test #3:

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

input:

2 1
X.

output:

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

result:

ok correct!

Test #4:

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

input:

1 2
.
X

output:

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

result:

ok correct!

Test #5:

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

input:

1 2
X
.

output:

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

result:

ok correct!

Test #6:

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

input:

2 1
XX

output:

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

result:

ok correct!

Test #7:

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

input:

3 3
XXX
X.X
XXX

output:

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

result:

ok correct!

Test #8:

score: 0
Accepted
time: 663ms
memory: 7012kb

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

input:

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

output:

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

result:

ok correct!

Test #10:

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

input:

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

output:

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

result:

ok correct!

Test #11:

score: 0
Accepted
time: 681ms
memory: 7812kb

input:

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

output:

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

result:

ok correct!

Test #12:

score: 0
Accepted
time: 692ms
memory: 7752kb

input:

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

output:

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

result:

ok correct!

Test #13:

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

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

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

input:

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

output:

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

result:

ok correct!

Test #16:

score: 0
Accepted
time: 246ms
memory: 4944kb

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

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

input:

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

output:

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

result:

ok correct!

Test #19:

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

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

input:

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

output:

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

result:

ok correct!

Test #21:

score: 0
Accepted
time: 265ms
memory: 4976kb

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

input:

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

output:

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

result:

ok correct!

Test #23:

score: 0
Accepted
time: 215ms
memory: 4188kb

input:

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

output:

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

result:

ok correct!

Test #24:

score: 0
Accepted
time: 223ms
memory: 4568kb

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

input:

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

output:

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

result:

ok correct!

Test #26:

score: 0
Accepted
time: 514ms
memory: 5632kb

input:

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

output:

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

result:

ok correct!

Test #27:

score: 0
Accepted
time: 446ms
memory: 5836kb

input:

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

output:

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

result:

ok correct!

Test #28:

score: 0
Accepted
time: 287ms
memory: 5144kb

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

input:

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

output:

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

result:

ok correct!

Test #30:

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

input:

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

output:

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

result:

ok correct!

Test #31:

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

input:

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

output:

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

result:

ok correct!

Test #32:

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

input:

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

output:

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

result:

ok correct!

Test #33:

score: 0
Accepted
time: 481ms
memory: 6648kb

input:

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

output:

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

result:

ok correct!

Test #34:

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

input:

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

output:

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

result:

ok correct!

Test #35:

score: 0
Accepted
time: 219ms
memory: 4532kb

input:

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

output:

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

result:

ok correct!

Test #36:

score: 0
Accepted
time: 207ms
memory: 4728kb

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

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

input:

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

output:

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

result:

ok correct!

Test #39:

score: 0
Accepted
time: 580ms
memory: 5984kb

input:

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

output:

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

result:

ok correct!

Test #40:

score: 0
Accepted
time: 277ms
memory: 3992kb

input:

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

output:

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

result:

ok correct!

Test #41:

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

input:

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

output:

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

result:

ok correct!

Test #42:

score: 0
Accepted
time: 370ms
memory: 5644kb

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

input:

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

output:

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

result:

ok correct!

Test #44:

score: 0
Accepted
time: 430ms
memory: 5548kb

input:

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

output:

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

result:

ok correct!

Test #45:

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

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

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

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

input:

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

output:

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

result:

ok correct!

Test #49:

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

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

input:

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

output:

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

result:

ok correct!

Test #51:

score: 0
Accepted
time: 295ms
memory: 4760kb

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

input:

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

output:

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

result:

ok correct!

Test #53:

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

input:

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

output:

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

result:

ok correct!

Test #54:

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

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

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

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

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

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

input:

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

output:

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

result:

ok correct!

Test #60:

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

input:

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

output:

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

result:

ok correct!

Test #61:

score: 0
Accepted
time: 200ms
memory: 4200kb

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

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

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

input:

1 2
X
X

output:

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

result:

ok correct!

Test #65:

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

input:

1 3
X
.
.

output:

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

result:

ok correct!

Test #66:

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

input:

1 3
.
X
.

output:

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

result:

ok correct!

Test #67:

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

input:

1 3
X
X
.

output:

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

result:

ok correct!

Test #68:

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

input:

1 3
.
.
X

output:

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

result:

ok correct!

Test #69:

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

input:

1 3
X
.
X

output:

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

result:

ok correct!

Test #70:

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

input:

1 3
.
X
X

output:

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

result:

ok correct!

Test #71:

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

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

input:

1 4
X
.
.
.

output:

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

result:

ok correct!

Test #73:

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

input:

1 4
.
X
.
.

output:

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

result:

ok correct!

Test #74:

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

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

input:

1 4
.
.
X
.

output:

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

result:

ok correct!

Test #76:

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

input:

1 4
X
.
X
.

output:

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

result:

ok correct!

Test #77:

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

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

input:

1 4
X
X
X
.

output:

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

result:

ok correct!

Test #79:

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

input:

1 4
.
.
.
X

output:

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

result:

ok correct!

Test #80:

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

input:

1 4
X
.
.
X

output:

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

result:

ok correct!

Test #81:

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

input:

1 4
.
X
.
X

output:

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

result:

ok correct!

Test #82:

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

input:

1 4
X
X
.
X

output:

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

result:

ok correct!

Test #83:

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

input:

1 4
.
.
X
X

output:

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

result:

ok correct!

Test #84:

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

input:

1 4
X
.
X
X

output:

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

result:

ok correct!

Test #85:

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

input:

1 4
.
X
X
X

output:

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

result:

ok correct!

Test #86:

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

input:

1 4
X
X
X
X

output:

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

result:

ok correct!

Test #87:

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

input:

2 2
X.
..

output:

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

result:

ok correct!

Test #88:

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

input:

2 2
.X
..

output:

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

result:

ok correct!

Test #89:

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

input:

2 2
XX
..

output:

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

result:

ok correct!

Test #90:

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

input:

2 2
..
X.

output:

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

result:

ok correct!

Test #91:

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

input:

2 2
X.
X.

output:

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

result:

ok correct!

Test #92:

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

input:

2 2
.X
X.

output:

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

result:

ok correct!

Test #93:

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

input:

2 2
XX
X.

output:

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

result:

ok correct!

Test #94:

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

input:

2 2
..
.X

output:

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

result:

ok correct!

Test #95:

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

input:

2 2
X.
.X

output:

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

result:

ok correct!

Test #96:

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

input:

2 2
.X
.X

output:

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

result:

ok correct!

Test #97:

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

input:

2 2
XX
.X

output:

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

result:

ok correct!

Test #98:

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

input:

2 2
..
XX

output:

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

result:

ok correct!

Test #99:

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

input:

2 2
X.
XX

output:

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

result:

ok correct!

Test #100:

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

input:

2 2
.X
XX

output:

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

result:

ok correct!

Test #101:

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

input:

2 2
XX
XX

output:

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

result:

ok correct!

Test #102:

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

input:

3 1
X..

output:

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

result:

ok correct!

Test #103:

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

input:

3 1
.X.

output:

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

result:

ok correct!

Test #104:

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

input:

3 1
XX.

output:

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

result:

ok correct!

Test #105:

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

input:

3 1
..X

output:

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

result:

ok correct!

Test #106:

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

input:

3 1
X.X

output:

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

result:

ok correct!

Test #107:

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

input:

3 1
.XX

output:

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

result:

ok correct!

Test #108:

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

input:

3 1
XXX

output:

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

result:

ok correct!

Test #109:

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

input:

4 1
X...

output:

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

result:

ok correct!

Test #110:

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

input:

4 1
.X..

output:

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

result:

ok correct!

Test #111:

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

input:

4 1
XX..

output:

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

result:

ok correct!

Test #112:

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

input:

4 1
..X.

output:

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

result:

ok correct!

Test #113:

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

input:

4 1
X.X.

output:

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

result:

ok correct!

Test #114:

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

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

input:

4 1
XXX.

output:

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

result:

ok correct!

Test #116:

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

input:

4 1
...X

output:

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

result:

ok correct!

Test #117:

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

input:

4 1
X..X

output:

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

result:

ok correct!

Test #118:

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

input:

4 1
.X.X

output:

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

result:

ok correct!

Test #119:

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

input:

4 1
XX.X

output:

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

result:

ok correct!

Test #120:

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

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

input:

4 1
X.XX

output:

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

result:

ok correct!

Test #122:

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

input:

4 1
.XXX

output:

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

result:

ok correct!

Test #123:

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

input:

4 1
XXXX

output:

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

result:

ok correct!

Test #124:

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

input:

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

output:

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

result:

ok correct!

Test #125:

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

input:

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

output:

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

result:

ok correct!

Test #126:

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

input:

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

output:

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

result:

ok correct!

Test #127:

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

input:

100 1
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

output:

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

result:

ok correct!

Test #128:

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

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

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

input:

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

output:

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

result:

ok correct!

Test #131:

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

input:

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

output:

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

result:

ok correct!

Test #132:

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

input:

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

output:

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

result:

ok correct!

Test #133:

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

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

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

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

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

input:

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

output:

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

result:

ok correct!

Test #138:

score: 0
Accepted
time: 673ms
memory: 7776kb

input:

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

output:

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

result:

ok correct!

Test #139:

score: 0
Accepted
time: 665ms
memory: 7732kb

input:

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

output:

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

result:

ok correct!

Test #140:

score: 0
Accepted
time: 679ms
memory: 7728kb

input:

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

output:

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

result:

ok correct!

Test #141:

score: 0
Accepted
time: 664ms
memory: 4024kb

input:

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

output:

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

result:

ok correct!

Test #142:

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

input:

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

output:

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

result:

ok correct!

Test #143:

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

input:

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

output:

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

result:

ok correct!

Test #144:

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

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

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

input:

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

output:

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

result:

ok correct!

Extra Test:

score: 0
Extra Test Passed