QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#536659#5112. Where Am I?RngBased#AC ✓31ms12048kbC++202.5kb2024-08-29 15:31:522024-08-29 15:31:53

Judging History

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

  • [2024-08-29 15:31:53]
  • 评测
  • 测评结果:AC
  • 用时:31ms
  • 内存:12048kb
  • [2024-08-29 15:31:52]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
int n, m;
ll total = 0, ans[205][205];
char arr[205][205];
vector<pii> X;
ll count(int x, int y, int nx, int ny){
    ll d = max(abs(nx - x), abs(ny - y));
    ll dis = max(2 * d - 1, 0LL) * max(2 * d - 1, 0LL);
    if (x == nx && y == ny)
        return 0;
    if (x == nx - d && y == ny - d)
        return dis + 8 * d - 1;
    if (x == nx - d)
        return dis + y - (ny - d) - 1;
    if (y == ny + d)
        return dis + 2 * d + x - (nx - d) - 1;
    if (x == nx + d)
        return dis + 4 * d + (ny + d) - y - 1;
    return dis + 6 * d + (nx + d) - x - 1;
}
ll solve(vector<ll> v1, vector<ll> v2){
    for (int i = 0; i < v1.size(); i++){
        if (v1[i] != v2[i])
            return min(v1[i], v2[i]);
    }
    return -1;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    swap(n, m);
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> arr[i][j];
            if (arr[i][j] == 'X')
                X.emplace_back(i, j);
        }
    }
    vector<pair<vector<ll>, pii> > comp;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            vector<ll> dis;
            for (auto [x, y] : X)
                dis.emplace_back(count(x, y, i, j));
            sort(all(dis));
            comp.emplace_back(dis, pii(i, j));
        }
    }
    sort(all(comp));
    ll big = -1;
    for (int i = 0; i < comp.size(); i++){
        ll ans1 = 0, ans2 = 0;
        if (i > 0)
            ans1 = solve(comp[i].F, comp[i - 1].F);
        if (i + 1 < comp.size())
            ans2 = solve(comp[i].F, comp[i + 1].F);
        ans[comp[i].S.F][comp[i].S.S] = max(ans1, ans2);
        total += max(ans1, ans2);
        big = max(big, max(ans1, ans2));
    }
    cout << fixed << setprecision(5) << (double)total / (n * m) << '\n';
    cout << big << '\n';
    vector<pii> res;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (ans[i][j] == big)
                res.emplace_back(j, n + 1 - i);
    sort(all(res), [](pii a, pii b){
        if (a.S != b.S)
            return a.S < b.S;
        return a.F < b.F;
    });
    for (auto [i, j] : res)
        cout << "(" << i << "," << j << ") ";
    cout << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 1
X

output:

0.00000
0
(1,1) 

result:

ok correct!

Test #2:

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

input:

2 1
.X

output:

0.00000
0
(1,1) (2,1) 

result:

ok correct!

Test #3:

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

input:

2 1
X.

output:

0.00000
0
(1,1) (2,1) 

result:

ok correct!

Test #4:

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

input:

1 2
.
X

output:

0.00000
0
(1,1) (1,2) 

result:

ok correct!

Test #5:

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

input:

1 2
X
.

output:

0.00000
0
(1,1) (1,2) 

result:

ok correct!

Test #6:

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

input:

2 1
XX

output:

3.00000
3
(1,1) (2,1) 

result:

ok correct!

Test #7:

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

input:

3 3
XXX
X.X
XXX

output:

3.11111
5
(3,1) (3,2) 

result:

ok correct!

Test #8:

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

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

result:

ok correct!

Test #9:

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

input:

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

output:

19735.31990
39599
(100,1) (100,2) 

result:

ok correct!

Test #10:

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

input:

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

output:

19865.66990
39500
(100,1) (100,2) 

result:

ok correct!

Test #11:

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

input:

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

output:

11855.63920
39302
(100,99) (99,100) 

result:

ok correct!

Test #12:

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

input:

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

output:

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

result:

ok correct!

Test #13:

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

input:

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

output:

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

input:

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

output:

100.71120
742
(1,1) (2,1) 

result:

ok correct!

Test #15:

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

input:

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

output:

494.49788
1503
(56,38) (56,39) 

result:

ok correct!

Test #16:

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

input:

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

output:

122.54531
387
(1,19) (19,32) 

result:

ok correct!

Test #17:

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

input:

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

output:

103.48744
334
(10,57) (11,57) 

result:

ok correct!

Test #18:

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

input:

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

output:

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

result:

ok correct!

Test #19:

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

input:

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

output:

79.14933
319
(1,39) (1,40) 

result:

ok correct!

Test #20:

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

input:

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

output:

383.80832
1084
(93,9) (51,51) 

result:

ok correct!

Test #21:

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

input:

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

output:

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

result:

ok correct!

Test #22:

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

input:

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

output:

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

result:

ok correct!

Test #23:

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

input:

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

output:

291.70603
860
(1,1) (1,50) 

result:

ok correct!

Test #24:

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

input:

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

output:

152.16188
512
(48,9) (48,67) 

result:

ok correct!

Test #25:

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

input:

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

output:

212.39625
1031
(1,67) (1,68) 

result:

ok correct!

Test #26:

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

input:

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

output:

357.12133
2687
(1,83) (1,84) 

result:

ok correct!

Test #27:

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

input:

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

output:

225.85552
975
(84,1) (85,1) 

result:

ok correct!

Test #28:

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

input:

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

output:

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

result:

ok correct!

Test #29:

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

input:

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

output:

738.97448
3378
(5,45) (5,56) 

result:

ok correct!

Test #30:

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

input:

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

output:

1550.39098
4192
(76,34) (76,96) 

result:

ok correct!

Test #31:

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

input:

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

output:

648.65022
2420
(16,1) (1,13) 

result:

ok correct!

Test #32:

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

input:

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

output:

207.33776
895
(1,97) (1,98) 

result:

ok correct!

Test #33:

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

input:

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

output:

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

result:

ok correct!

Test #34:

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

input:

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

output:

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

result:

ok correct!

Test #35:

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

input:

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

output:

142.15382
673
(1,74) (2,74) 

result:

ok correct!

Test #36:

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

input:

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

output:

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

result:

ok correct!

Test #37:

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

input:

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

output:

81.66998
314
(1,64) (1,65) 

result:

ok correct!

Test #38:

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

input:

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

output:

300.30753
1326
(39,93) (40,93) 

result:

ok correct!

Test #39:

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

input:

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

output:

474.06897
2063
(1,1) (49,1) 

result:

ok correct!

Test #40:

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

input:

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

output:

2555.36748
5914
(46,1) (46,2) 

result:

ok correct!

Test #41:

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

input:

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

output:

2389.20036
11288
(21,60) (22,60) 

result:

ok correct!

Test #42:

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

input:

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

output:

225.08916
803
(10,61) (11,61) 

result:

ok correct!

Test #43:

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

input:

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

output:

213.68757
941
(33,89) (33,90) 

result:

ok correct!

Test #44:

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

input:

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

output:

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

result:

ok correct!

Test #45:

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

input:

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

output:

67.35474
645
(1,1) (2,1) 

result:

ok correct!

Test #46:

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

input:

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

output:

80.04103
332
(64,34) (65,34) 

result:

ok correct!

Test #47:

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

input:

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

output:

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

result:

ok correct!

Test #48:

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

input:

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

output:

302.78985
799
(87,29) (87,58) 

result:

ok correct!

Test #49:

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

input:

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

output:

150.34691
930
(52,44) (53,44) 

result:

ok correct!

Test #50:

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

input:

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

output:

690.64641
3826
(1,96) (1,97) 

result:

ok correct!

Test #51:

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

input:

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

output:

356.97458
1620
(23,68) (51,68) 

result:

ok correct!

Test #52:

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

input:

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

output:

1705.10220
4664
(100,44) (100,90) 

result:

ok correct!

Test #53:

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

input:

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

output:

2976.14232
8305
(68,1) (69,1) 

result:

ok correct!

Test #54:

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

input:

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

output:

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

result:

ok correct!

Test #55:

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

input:

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

output:

179.27925
713
(98,56) (98,57) 

result:

ok correct!

Test #56:

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

input:

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

output:

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

result:

ok correct!

Test #57:

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

input:

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

output:

115.94057
390
(15,48) (79,48) 

result:

ok correct!

Test #58:

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

input:

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

output:

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

result:

ok correct!

Test #59:

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

input:

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

output:

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

result:

ok correct!

Test #60:

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

input:

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

output:

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

result:

ok correct!

Test #61:

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

input:

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

output:

164.87808
772
(1,7) (1,8) 

result:

ok correct!

Test #62:

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

input:

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

output:

106.01294
560
(1,1) (1,2) 

result:

ok correct!

Test #63:

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

input:

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

output:

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

result:

ok correct!

Test #64:

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

input:

1 2
X
X

output:

1.00000
1
(1,1) (1,2) 

result:

ok correct!

Test #65:

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

input:

1 3
X
.
.

output:

0.66667
1
(1,1) (1,2) 

result:

ok correct!

Test #66:

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

input:

1 3
.
X
.

output:

0.66667
1
(1,1) (1,3) 

result:

ok correct!

Test #67:

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

input:

1 3
X
X
.

output:

0.66667
1
(1,2) (1,3) 

result:

ok correct!

Test #68:

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

input:

1 3
.
.
X

output:

3.33333
5
(1,2) (1,3) 

result:

ok correct!

Test #69:

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

input:

1 3
X
.
X

output:

6.66667
10
(1,1) (1,3) 

result:

ok correct!

Test #70:

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

input:

1 3
.
X
X

output:

0.66667
1
(1,1) (1,2) 

result:

ok correct!

Test #71:

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

input:

1 3
X
X
X

output:

3.66667
5
(1,1) (1,2) 

result:

ok correct!

Test #72:

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

input:

1 4
X
.
.
.

output:

5.25000
10
(1,1) (1,2) 

result:

ok correct!

Test #73:

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

input:

1 4
.
X
.
.

output:

2.75000
5
(1,1) (1,4) 

result:

ok correct!

Test #74:

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

input:

1 4
X
X
.
.

output:

1.00000
1
(1,1) (1,2) (1,3) (1,4) 

result:

ok correct!

Test #75:

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

input:

1 4
.
.
X
.

output:

2.75000
5
(1,3) (1,4) 

result:

ok correct!

Test #76:

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

input:

1 4
X
.
X
.

output:

7.50000
10
(1,2) (1,4) 

result:

ok correct!

Test #77:

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

input:

1 4
.
X
X
.

output:

1.00000
1
(1,1) (1,2) (1,3) (1,4) 

result:

ok correct!

Test #78:

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

input:

1 4
X
X
X
.

output:

2.75000
5
(1,2) (1,3) 

result:

ok correct!

Test #79:

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

input:

1 4
.
.
.
X

output:

10.25000
18
(1,3) (1,4) 

result:

ok correct!

Test #80:

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

input:

1 4
X
.
.
X

output:

14.00000
27
(1,1) (1,4) 

result:

ok correct!

Test #81:

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

input:

1 4
.
X
.
X

output:

5.50000
10
(1,1) (1,3) 

result:

ok correct!

Test #82:

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

input:

1 4
X
X
.
X

output:

2.75000
5
(1,1) (1,4) 

result:

ok correct!

Test #83:

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

input:

1 4
.
.
X
X

output:

3.00000
5
(1,3) (1,4) 

result:

ok correct!

Test #84:

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

input:

1 4
X
.
X
X

output:

2.75000
5
(1,2) (1,4) 

result:

ok correct!

Test #85:

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

input:

1 4
.
X
X
X

output:

2.75000
5
(1,1) (1,2) 

result:

ok correct!

Test #86:

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

input:

1 4
X
X
X
X

output:

6.50000
10
(1,2) (1,3) 

result:

ok correct!

Test #87:

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

input:

2 2
X.
..

output:

3.75000
7
(2,1) (2,2) 

result:

ok correct!

Test #88:

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

input:

2 2
.X
..

output:

1.25000
2
(1,1) (1,2) 

result:

ok correct!

Test #89:

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

input:

2 2
XX
..

output:

2.50000
3
(1,2) (2,2) 

result:

ok correct!

Test #90:

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

input:

2 2
..
X.

output:

4.25000
6
(2,1) (2,2) 

result:

ok correct!

Test #91:

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

input:

2 2
X.
X.

output:

3.50000
6
(2,1) (2,2) 

result:

ok correct!

Test #92:

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

input:

2 2
.X
X.

output:

1.50000
2
(1,1) (2,2) 

result:

ok correct!

Test #93:

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

input:

2 2
XX
X.

output:

1.75000
3
(1,2) (2,2) 

result:

ok correct!

Test #94:

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

input:

2 2
..
.X

output:

2.75000
4
(1,2) (2,2) 

result:

ok correct!

Test #95:

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

input:

2 2
X.
.X

output:

2.50000
4
(2,1) (1,2) 

result:

ok correct!

Test #96:

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

input:

2 2
.X
.X

output:

1.50000
2
(1,1) (1,2) 

result:

ok correct!

Test #97:

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

input:

2 2
XX
.X

output:

1.75000
3
(1,2) (2,2) 

result:

ok correct!

Test #98:

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

input:

2 2
..
XX

output:

3.50000
4
(1,2) (2,2) 

result:

ok correct!

Test #99:

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

input:

2 2
X.
XX

output:

2.25000
4
(2,1) (1,2) 

result:

ok correct!

Test #100:

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

input:

2 2
.X
XX

output:

1.25000
2
(1,1) (2,2) 

result:

ok correct!

Test #101:

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

input:

2 2
XX
XX

output:

2.50000
3
(1,2) (2,2) 

result:

ok correct!

Test #102:

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

input:

3 1
X..

output:

4.66667
7
(2,1) (3,1) 

result:

ok correct!

Test #103:

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

input:

3 1
.X.

output:

2.00000
3
(1,1) (3,1) 

result:

ok correct!

Test #104:

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

input:

3 1
XX.

output:

2.00000
3
(1,1) (2,1) 

result:

ok correct!

Test #105:

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

input:

3 1
..X

output:

2.00000
3
(1,1) (2,1) 

result:

ok correct!

Test #106:

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

input:

3 1
X.X

output:

9.33333
14
(1,1) (3,1) 

result:

ok correct!

Test #107:

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

input:

3 1
.XX

output:

2.00000
3
(2,1) (3,1) 

result:

ok correct!

Test #108:

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

input:

3 1
XXX

output:

5.66667
7
(1,1) (2,1) 

result:

ok correct!

Test #109:

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

input:

4 1
X...

output:

12.75000
22
(3,1) (4,1) 

result:

ok correct!

Test #110:

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

input:

4 1
.X..

output:

4.25000
7
(3,1) (4,1) 

result:

ok correct!

Test #111:

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

input:

4 1
XX..

output:

5.00000
7
(3,1) (4,1) 

result:

ok correct!

Test #112:

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

input:

4 1
..X.

output:

4.25000
7
(1,1) (4,1) 

result:

ok correct!

Test #113:

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

input:

4 1
X.X.

output:

8.50000
14
(1,1) (3,1) 

result:

ok correct!

Test #114:

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

input:

4 1
.XX.

output:

3.00000
3
(1,1) (2,1) (3,1) (4,1) 

result:

ok correct!

Test #115:

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

input:

4 1
XXX.

output:

4.25000
7
(1,1) (2,1) 

result:

ok correct!

Test #116:

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

input:

4 1
...X

output:

7.75000
14
(1,1) (2,1) 

result:

ok correct!

Test #117:

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

input:

4 1
X..X

output:

18.00000
33
(1,1) (4,1) 

result:

ok correct!

Test #118:

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

input:

4 1
.X.X

output:

10.50000
14
(2,1) (4,1) 

result:

ok correct!

Test #119:

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

input:

4 1
XX.X

output:

4.25000
7
(2,1) (4,1) 

result:

ok correct!

Test #120:

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

input:

4 1
..XX

output:

3.00000
3
(1,1) (2,1) (3,1) (4,1) 

result:

ok correct!

Test #121:

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

input:

4 1
X.XX

output:

4.25000
7
(1,1) (4,1) 

result:

ok correct!

Test #122:

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

input:

4 1
.XXX

output:

4.25000
7
(2,1) (3,1) 

result:

ok correct!

Test #123:

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

input:

4 1
XXXX

output:

9.50000
14
(2,1) (3,1) 

result:

ok correct!

Test #124:

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

input:

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

output:

13274.59000
38710
(99,1) (100,1) 

result:

ok correct!

Test #125:

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

input:

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

output:

13076.63000
38318
(1,1) (2,1) 

result:

ok correct!

Test #126:

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

input:

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

output:

3356.01000
9751
(1,1) (100,1) 

result:

ok correct!

Test #127:

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

input:

100 1
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

output:

3457.50000
9950
(50,1) (51,1) 

result:

ok correct!

Test #128:

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

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

result:

ok correct!

Test #129:

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

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

result:

ok correct!

Test #130:

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

input:

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

output:

12977.65000
38122
(1,1) (1,2) 

result:

ok correct!

Test #131:

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

input:

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

output:

13175.61000
38514
(1,99) (1,100) 

result:

ok correct!

Test #132:

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

input:

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

output:

3306.03000
9653
(1,99) (1,100) 

result:

ok correct!

Test #133:

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

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

result:

ok correct!

Test #134:

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

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

result:

ok correct!

Test #135:

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

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

result:

ok correct!

Test #136:

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

input:

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

output:

58.08000
95
(5,10) (6,10) 

result:

ok correct!

Test #137:

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

input:

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

output:

13878.92750
38908
(99,1) (100,1) 

result:

ok correct!

Test #138:

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

input:

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

output:

14059.27250
39302
(99,100) (100,100) 

result:

ok correct!

Test #139:

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

input:

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

output:

14132.28250
39500
(100,1) (100,2) 

result:

ok correct!

Test #140:

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

input:

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

output:

13951.43250
39104
(1,99) (1,100) 

result:

ok correct!

Test #141:

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

input:

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

output:

19733.33990
39302
(99,100) (100,100) 

result:

ok correct!

Test #142:

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

input:

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

output:

19601.00990
39104
(1,99) (1,100) 

result:

ok correct!

Test #143:

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

input:

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

output:

5001.48990
10098
(99,100) (100,100) 

result:

ok correct!

Test #144:

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

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

result:

ok correct!

Test #145:

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

input:

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

output:

60.83080
195
(28,1) (1,35) 

result:

ok correct!

Test #146:

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

input:

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

output:

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

result:

ok correct!

Extra Test:

score: 0
Extra Test Passed