QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#380222#5112. Where Am I?cciafrino#AC ✓112ms12424kbC++202.7kb2024-04-06 21:56:222024-04-06 21:56:22

Judging History

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

  • [2024-04-06 21:56:22]
  • 评测
  • 测评结果:AC
  • 用时:112ms
  • 内存:12424kb
  • [2024-04-06 21:56:22]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 105;
int ans[MAXN][MAXN];
map<pair<int, int>, int> mapa;
vector<int> v[MAXN][MAXN];
vector<int> dx = {-1, 0, 1, 0};
vector<int> dy = {0, 1, 0, -1};
int N, M;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> N >> M;

    vector<string> G(M); for (auto& s : G) cin >> s;

    int x = 0, y = 0, cur = 1;
    for (int i = 1; i < MAXN; ++i) {
        for (int dir : {0, 1, 2, 3}) {
            int offset = 0;
            if (dir < 2) offset++;
            for (int g = 2*i - offset; g > 0; --g) {
                x += dx[dir];
                y += dy[dir];
                mapa[{x, y}] = cur++;
            }
        }
    }

    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            if (G[i][j] != 'X') continue;

            for (int ii = 0; ii < M; ++ii) {
                for (int jj = 0; jj < N; ++jj) {
                    int h = mapa[{i - ii, j - jj}];
                    v[ii][jj].push_back(h);
                }
            }
        }
    }

    vector<pair<int, int>> idx;
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            sort(v[i][j].begin(), v[i][j].end());
            idx.push_back({i, j});
        }
    }

    sort(idx.begin(), idx.end(), [&](const auto& l, const auto& r) {
        return v[l.first][l.second] < v[r.first][r.second];
    });

    // cout << "WOW" << endl;
    for (int g = 1; g < N*M; ++g) {
        int xx = idx[g].first;
        int yy = idx[g].second;
        x = idx[g-1].first;
        y = idx[g-1].second;

        bool found = false;
        int l = 0;
        while (true) {
            if (found) break;
            auto a = v[x][y][l];
            auto b = v[xx][yy][l++];
            // cout << a << ' ' << b << endl;
            if (a != b) {
                ans[x][y] = max(ans[x][y], min(a, b));
                ans[xx][yy] = max(ans[xx][yy], min(a, b));
                found = true;
            }
        }
    }

    int sum = 0;
    int max_val = 0;
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            sum += ans[i][j];
            max_val = max(max_val, ans[i][j]);
        }
    }

    cout << fixed << setprecision(20);
    cout << 1.0 * sum / N / M << '\n';
    cout << max_val << '\n';

    vector<pair<int, int>> pnts;
    for (int i = M-1; i >= 0; --i) {
        for (int j = 0; j < N; ++j) {
            if (ans[i][j] != max_val) continue;
            pnts.push_back({j, M-1-i});
        }
    }

    int s = 0;
    for (auto [a, b] : pnts) {
        if (s != 0) cout << ' ';
        cout << "(" << a+1 << ',' << b+1 << ")";
        s += 1;
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 8ms
memory: 6552kb

input:

1 1
X

output:

0.00000000000000000000
0
(1,1)

result:

ok correct!

Test #2:

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

input:

2 1
.X

output:

0.00000000000000000000
0
(1,1) (2,1)

result:

ok correct!

Test #3:

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

input:

2 1
X.

output:

0.00000000000000000000
0
(1,1) (2,1)

result:

ok correct!

Test #4:

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

input:

1 2
.
X

output:

0.00000000000000000000
0
(1,1) (1,2)

result:

ok correct!

Test #5:

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

input:

1 2
X
.

output:

0.00000000000000000000
0
(1,1) (1,2)

result:

ok correct!

Test #6:

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

input:

2 1
XX

output:

3.00000000000000000000
3
(1,1) (2,1)

result:

ok correct!

Test #7:

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

input:

3 3
XXX
X.X
XXX

output:

3.11111111111111116045
5
(3,1) (3,2)

result:

ok correct!

Test #8:

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

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

result:

ok correct!

Test #9:

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

input:

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

output:

19735.31989999999859719537
39599
(100,1) (100,2)

result:

ok correct!

Test #10:

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

input:

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

output:

19865.66990000000077998266
39500
(100,1) (100,2)

result:

ok correct!

Test #11:

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

input:

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

output:

11855.63919999999961873982
39302
(100,99) (99,100)

result:

ok correct!

Test #12:

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

input:

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

output:

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

result:

ok correct!

Test #13:

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

input:

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

output:

50.09794520547945495537
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: 35ms
memory: 8672kb

input:

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

output:

100.71120107962214262898
742
(1,1) (2,1)

result:

ok correct!

Test #15:

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

input:

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

output:

494.49788135593217930364
1503
(56,38) (56,39)

result:

ok correct!

Test #16:

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

input:

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

output:

122.54531168150865028110
387
(1,19) (19,32)

result:

ok correct!

Test #17:

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

input:

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

output:

103.48744410044720609676
334
(10,57) (11,57)

result:

ok correct!

Test #18:

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

input:

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

output:

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

result:

ok correct!

Test #19:

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

input:

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

output:

79.14933333333333109749
319
(1,39) (1,40)

result:

ok correct!

Test #20:

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

input:

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

output:

383.80832378770526247536
1084
(93,9) (51,51)

result:

ok correct!

Test #21:

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

input:

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

output:

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

result:

ok correct!

Test #22:

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

input:

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

output:

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

result:

ok correct!

Test #23:

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

input:

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

output:

291.70602945262572802676
860
(1,1) (1,50)

result:

ok correct!

Test #24:

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

input:

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

output:

152.16188063063063395930
512
(48,9) (48,67)

result:

ok correct!

Test #25:

score: 0
Accepted
time: 112ms
memory: 11976kb

input:

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

output:

212.39625000000000909495
1031
(1,67) (1,68)

result:

ok correct!

Test #26:

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

input:

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

output:

357.12132725430598156890
2687
(1,83) (1,84)

result:

ok correct!

Test #27:

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

input:

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

output:

225.85552325581392096865
975
(84,1) (85,1)

result:

ok correct!

Test #28:

score: 0
Accepted
time: 49ms
memory: 9228kb

input:

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

output:

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

result:

ok correct!

Test #29:

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

input:

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

output:

738.97447963800902925868
3378
(5,45) (5,56)

result:

ok correct!

Test #30:

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

input:

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

output:

1550.39097744360901742766
4192
(76,34) (76,96)

result:

ok correct!

Test #31:

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

input:

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

output:

648.65021665864219357900
2420
(16,1) (1,13)

result:

ok correct!

Test #32:

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

input:

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

output:

207.33775510204080205767
895
(1,97) (1,98)

result:

ok correct!

Test #33:

score: 0
Accepted
time: 71ms
memory: 10712kb

input:

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

output:

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

result:

ok correct!

Test #34:

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

input:

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

output:

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

result:

ok correct!

Test #35:

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

input:

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

output:

142.15382403680277434432
673
(1,74) (2,74)

result:

ok correct!

Test #36:

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

input:

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

output:

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

result:

ok correct!

Test #37:

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

input:

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

output:

81.66998491704374885103
314
(1,64) (1,65)

result:

ok correct!

Test #38:

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

input:

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

output:

300.30752688172043463055
1326
(39,93) (40,93)

result:

ok correct!

Test #39:

score: 0
Accepted
time: 60ms
memory: 11528kb

input:

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

output:

474.06896551724139499129
2063
(1,1) (49,1)

result:

ok correct!

Test #40:

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

input:

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

output:

2555.36748381128563778475
5914
(46,1) (46,2)

result:

ok correct!

Test #41:

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

input:

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

output:

2389.20035842293918904033
11288
(21,60) (22,60)

result:

ok correct!

Test #42:

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

input:

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

output:

225.08916025426563578549
803
(10,61) (11,61)

result:

ok correct!

Test #43:

score: 0
Accepted
time: 82ms
memory: 11624kb

input:

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

output:

213.68756998880178343825
941
(33,89) (33,90)

result:

ok correct!

Test #44:

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

input:

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

output:

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

result:

ok correct!

Test #45:

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

input:

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

output:

67.35474308300395307469
645
(1,1) (2,1)

result:

ok correct!

Test #46:

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

input:

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

output:

80.04102564102564087989
332
(64,34) (65,34)

result:

ok correct!

Test #47:

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

input:

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

output:

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

result:

ok correct!

Test #48:

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

input:

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

output:

302.78984674329501558532
799
(87,29) (87,58)

result:

ok correct!

Test #49:

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

input:

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

output:

150.34691252144082795894
930
(52,44) (53,44)

result:

ok correct!

Test #50:

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

input:

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

output:

690.64641368721208891657
3826
(1,96) (1,97)

result:

ok correct!

Test #51:

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

input:

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

output:

356.97457983193277186729
1620
(23,68) (51,68)

result:

ok correct!

Test #52:

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

input:

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

output:

1705.10219780219767926610
4664
(100,44) (100,90)

result:

ok correct!

Test #53:

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

input:

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

output:

2976.14231601731626142282
8305
(68,1) (69,1)

result:

ok correct!

Test #54:

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

input:

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

output:

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

result:

ok correct!

Test #55:

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

input:

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

output:

179.27925170068024840475
713
(98,56) (98,57)

result:

ok correct!

Test #56:

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

input:

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

output:

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

result:

ok correct!

Test #57:

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

input:

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

output:

115.94057017543859444686
390
(15,48) (79,48)

result:

ok correct!

Test #58:

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

input:

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

output:

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

result:

ok correct!

Test #59:

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

input:

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

output:

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

result:

ok correct!

Test #60:

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

input:

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

output:

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

result:

ok correct!

Test #61:

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

input:

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

output:

164.87807807807806170786
772
(1,7) (1,8)

result:

ok correct!

Test #62:

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

input:

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

output:

106.01293759512937242562
560
(1,1) (1,2)

result:

ok correct!

Test #63:

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

input:

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

output:

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

result:

ok correct!

Test #64:

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

input:

1 2
X
X

output:

1.00000000000000000000
1
(1,1) (1,2)

result:

ok correct!

Test #65:

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

input:

1 3
X
.
.

output:

0.66666666666666662966
1
(1,1) (1,2)

result:

ok correct!

Test #66:

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

input:

1 3
.
X
.

output:

0.66666666666666662966
1
(1,1) (1,3)

result:

ok correct!

Test #67:

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

input:

1 3
X
X
.

output:

0.66666666666666662966
1
(1,2) (1,3)

result:

ok correct!

Test #68:

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

input:

1 3
.
.
X

output:

3.33333333333333348136
5
(1,2) (1,3)

result:

ok correct!

Test #69:

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

input:

1 3
X
.
X

output:

6.66666666666666696273
10
(1,1) (1,3)

result:

ok correct!

Test #70:

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

input:

1 3
.
X
X

output:

0.66666666666666662966
1
(1,1) (1,2)

result:

ok correct!

Test #71:

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

input:

1 3
X
X
X

output:

3.66666666666666651864
5
(1,1) (1,2)

result:

ok correct!

Test #72:

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

input:

1 4
X
.
.
.

output:

5.25000000000000000000
10
(1,1) (1,2)

result:

ok correct!

Test #73:

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

input:

1 4
.
X
.
.

output:

2.75000000000000000000
5
(1,1) (1,4)

result:

ok correct!

Test #74:

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

input:

1 4
X
X
.
.

output:

1.00000000000000000000
1
(1,1) (1,2) (1,3) (1,4)

result:

ok correct!

Test #75:

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

input:

1 4
.
.
X
.

output:

2.75000000000000000000
5
(1,3) (1,4)

result:

ok correct!

Test #76:

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

input:

1 4
X
.
X
.

output:

7.50000000000000000000
10
(1,2) (1,4)

result:

ok correct!

Test #77:

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

input:

1 4
.
X
X
.

output:

1.00000000000000000000
1
(1,1) (1,2) (1,3) (1,4)

result:

ok correct!

Test #78:

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

input:

1 4
X
X
X
.

output:

2.75000000000000000000
5
(1,2) (1,3)

result:

ok correct!

Test #79:

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

input:

1 4
.
.
.
X

output:

10.25000000000000000000
18
(1,3) (1,4)

result:

ok correct!

Test #80:

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

input:

1 4
X
.
.
X

output:

14.00000000000000000000
27
(1,1) (1,4)

result:

ok correct!

Test #81:

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

input:

1 4
.
X
.
X

output:

5.50000000000000000000
10
(1,1) (1,3)

result:

ok correct!

Test #82:

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

input:

1 4
X
X
.
X

output:

2.75000000000000000000
5
(1,1) (1,4)

result:

ok correct!

Test #83:

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

input:

1 4
.
.
X
X

output:

3.00000000000000000000
5
(1,3) (1,4)

result:

ok correct!

Test #84:

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

input:

1 4
X
.
X
X

output:

2.75000000000000000000
5
(1,2) (1,4)

result:

ok correct!

Test #85:

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

input:

1 4
.
X
X
X

output:

2.75000000000000000000
5
(1,1) (1,2)

result:

ok correct!

Test #86:

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

input:

1 4
X
X
X
X

output:

6.50000000000000000000
10
(1,2) (1,3)

result:

ok correct!

Test #87:

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

input:

2 2
X.
..

output:

3.75000000000000000000
7
(2,1) (2,2)

result:

ok correct!

Test #88:

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

input:

2 2
.X
..

output:

1.25000000000000000000
2
(1,1) (1,2)

result:

ok correct!

Test #89:

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

input:

2 2
XX
..

output:

2.50000000000000000000
3
(1,2) (2,2)

result:

ok correct!

Test #90:

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

input:

2 2
..
X.

output:

4.25000000000000000000
6
(2,1) (2,2)

result:

ok correct!

Test #91:

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

input:

2 2
X.
X.

output:

3.50000000000000000000
6
(2,1) (2,2)

result:

ok correct!

Test #92:

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

input:

2 2
.X
X.

output:

1.50000000000000000000
2
(1,1) (2,2)

result:

ok correct!

Test #93:

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

input:

2 2
XX
X.

output:

1.75000000000000000000
3
(1,2) (2,2)

result:

ok correct!

Test #94:

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

input:

2 2
..
.X

output:

2.75000000000000000000
4
(1,2) (2,2)

result:

ok correct!

Test #95:

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

input:

2 2
X.
.X

output:

2.50000000000000000000
4
(2,1) (1,2)

result:

ok correct!

Test #96:

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

input:

2 2
.X
.X

output:

1.50000000000000000000
2
(1,1) (1,2)

result:

ok correct!

Test #97:

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

input:

2 2
XX
.X

output:

1.75000000000000000000
3
(1,2) (2,2)

result:

ok correct!

Test #98:

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

input:

2 2
..
XX

output:

3.50000000000000000000
4
(1,2) (2,2)

result:

ok correct!

Test #99:

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

input:

2 2
X.
XX

output:

2.25000000000000000000
4
(2,1) (1,2)

result:

ok correct!

Test #100:

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

input:

2 2
.X
XX

output:

1.25000000000000000000
2
(1,1) (2,2)

result:

ok correct!

Test #101:

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

input:

2 2
XX
XX

output:

2.50000000000000000000
3
(1,2) (2,2)

result:

ok correct!

Test #102:

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

input:

3 1
X..

output:

4.66666666666666696273
7
(2,1) (3,1)

result:

ok correct!

Test #103:

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

input:

3 1
.X.

output:

2.00000000000000000000
3
(1,1) (3,1)

result:

ok correct!

Test #104:

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

input:

3 1
XX.

output:

2.00000000000000000000
3
(1,1) (2,1)

result:

ok correct!

Test #105:

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

input:

3 1
..X

output:

2.00000000000000000000
3
(1,1) (2,1)

result:

ok correct!

Test #106:

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

input:

3 1
X.X

output:

9.33333333333333392545
14
(1,1) (3,1)

result:

ok correct!

Test #107:

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

input:

3 1
.XX

output:

2.00000000000000000000
3
(2,1) (3,1)

result:

ok correct!

Test #108:

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

input:

3 1
XXX

output:

5.66666666666666696273
7
(1,1) (2,1)

result:

ok correct!

Test #109:

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

input:

4 1
X...

output:

12.75000000000000000000
22
(3,1) (4,1)

result:

ok correct!

Test #110:

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

input:

4 1
.X..

output:

4.25000000000000000000
7
(3,1) (4,1)

result:

ok correct!

Test #111:

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

input:

4 1
XX..

output:

5.00000000000000000000
7
(3,1) (4,1)

result:

ok correct!

Test #112:

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

input:

4 1
..X.

output:

4.25000000000000000000
7
(1,1) (4,1)

result:

ok correct!

Test #113:

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

input:

4 1
X.X.

output:

8.50000000000000000000
14
(1,1) (3,1)

result:

ok correct!

Test #114:

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

input:

4 1
.XX.

output:

3.00000000000000000000
3
(1,1) (2,1) (3,1) (4,1)

result:

ok correct!

Test #115:

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

input:

4 1
XXX.

output:

4.25000000000000000000
7
(1,1) (2,1)

result:

ok correct!

Test #116:

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

input:

4 1
...X

output:

7.75000000000000000000
14
(1,1) (2,1)

result:

ok correct!

Test #117:

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

input:

4 1
X..X

output:

18.00000000000000000000
33
(1,1) (4,1)

result:

ok correct!

Test #118:

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

input:

4 1
.X.X

output:

10.50000000000000000000
14
(2,1) (4,1)

result:

ok correct!

Test #119:

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

input:

4 1
XX.X

output:

4.25000000000000000000
7
(2,1) (4,1)

result:

ok correct!

Test #120:

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

input:

4 1
..XX

output:

3.00000000000000000000
3
(1,1) (2,1) (3,1) (4,1)

result:

ok correct!

Test #121:

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

input:

4 1
X.XX

output:

4.25000000000000000000
7
(1,1) (4,1)

result:

ok correct!

Test #122:

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

input:

4 1
.XXX

output:

4.25000000000000000000
7
(2,1) (3,1)

result:

ok correct!

Test #123:

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

input:

4 1
XXXX

output:

9.50000000000000000000
14
(2,1) (3,1)

result:

ok correct!

Test #124:

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

input:

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

output:

13274.59000000000014551915
38710
(99,1) (100,1)

result:

ok correct!

Test #125:

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

input:

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

output:

13076.62999999999919964466
38318
(1,1) (2,1)

result:

ok correct!

Test #126:

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

input:

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

output:

3356.01000000000021827873
9751
(1,1) (100,1)

result:

ok correct!

Test #127:

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

input:

100 1
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

output:

3457.50000000000000000000
9950
(50,1) (51,1)

result:

ok correct!

Test #128:

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

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

result:

ok correct!

Test #129:

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

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

result:

ok correct!

Test #130:

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

input:

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

output:

12977.64999999999963620212
38122
(1,1) (1,2)

result:

ok correct!

Test #131:

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

input:

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

output:

13175.61000000000058207661
38514
(1,99) (1,100)

result:

ok correct!

Test #132:

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

input:

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

output:

3306.03000000000020008883
9653
(1,99) (1,100)

result:

ok correct!

Test #133:

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

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

result:

ok correct!

Test #134:

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

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

result:

ok correct!

Test #135:

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

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

result:

ok correct!

Test #136:

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

input:

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

output:

58.07999999999999829470
95
(5,10) (6,10)

result:

ok correct!

Test #137:

score: 0
Accepted
time: 91ms
memory: 12424kb

input:

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

output:

13878.92749999999978172127
38908
(99,1) (100,1)

result:

ok correct!

Test #138:

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

input:

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

output:

14059.27249999999912688509
39302
(99,100) (100,100)

result:

ok correct!

Test #139:

score: 0
Accepted
time: 101ms
memory: 12292kb

input:

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

output:

14132.28249999999934516381
39500
(100,1) (100,2)

result:

ok correct!

Test #140:

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

input:

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

output:

13951.43250000000080035534
39104
(1,99) (1,100)

result:

ok correct!

Test #141:

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

input:

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

output:

19733.33989999999903375283
39302
(99,100) (100,100)

result:

ok correct!

Test #142:

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

input:

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

output:

19601.00990000000092550181
39104
(1,99) (1,100)

result:

ok correct!

Test #143:

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

input:

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

output:

5001.48989999999957944965
10098
(99,100) (100,100)

result:

ok correct!

Test #144:

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

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

result:

ok correct!

Test #145:

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

input:

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

output:

60.83079999999999643023
195
(28,1) (1,35)

result:

ok correct!

Test #146:

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

input:

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

output:

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

result:

ok correct!

Extra Test:

score: 0
Extra Test Passed