QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#385494#5112. Where Am I?SolitaryDream#AC ✓23ms8424kbC++172.2kb2024-04-10 19:59:282024-04-10 19:59:28

Judging History

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

  • [2024-04-10 19:59:28]
  • 评测
  • 测评结果:AC
  • 用时:23ms
  • 内存:8424kb
  • [2024-04-10 19:59:28]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 105;
int dx, dy;
int mp[N][N];
inline int Sqr(int x) {
    return x * x;
}
inline int Dis(int x, int y, int i, int j) {
    if (x == i && y == j) return 0;
    int d1 = max(abs(x - i), abs(y - j));
    int area = Sqr(2 * d1 - 1); 
    if (x != i - d1 && y == j + d1) return area + (x - (i - d1 + 1));
    if (x == i + d1) return area + d1 * 2 + ((j + d1 - 1) - y);
    if (y == j - d1) return area + d1 * 4 + ((i + d1 - 1) - x);
    if (x == i - d1) return area + d1 * 6 + (y - (j - d1 + 1));
    assert(0);  
}
inline int Calc(const vector<int> &a, const vector<int> &b) {
    int i = 0;
    while (a[i] == b[i]) ++i;
    return min(a[i], b[i]);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed << setprecision(15);
    cin >> dx >> dy;
    vector<pii> mark;
    for (int j = dy; j; --j) {
        static string str;
        cin >> str;
        for (int i = 1; i <= dx; ++i) {
            mp[i][j] = str[i - 1];
            if (mp[i][j] == 'X') mark.push_back({i, j}); 
        }
    }
    vector<pair<vector<int>, pii>> lst; 
    for (int i = 1; i <= dx; ++i)
        for (int j = 1; j <= dy; ++j) {
            vector<int> hs;
            for (auto [x, y] : mark) hs.push_back(Dis(x, y, i, j));
            sort(hs.begin(), hs.end());
            lst.push_back({hs, pii(i, j)});
        }
    sort(lst.begin(), lst.end());
    vector<tuple<int, int, int>> ans;
    int sm = 0;
    for (int i = 0; i < lst.size(); ++i) {
        int lcp = 0;
        if (i) lcp = max(lcp, Calc(lst[i].first, lst[i - 1].first));
        if (i + 1 < lst.size()) lcp = max(lcp, Calc(lst[i].first, lst[i + 1].first));
        auto [x, y] = lst[i].second;
        ans.push_back({lcp, y, x});
        sm += lcp;
    }
    sort(ans.begin(), ans.end());
    cout << double(sm) / lst.size() << endl;
    auto [rst, _y, _x] = ans.back();
    cout << rst << endl;
    auto it = lower_bound(ans.begin(), ans.end(), tuple<int, int, int>{rst, 0, 0});
    for (; it != ans.end(); ++it) {
        auto [_rst, y, x] = *it;
        cout << '(' << x << ',' << y << ')' << ' ';
    }
    cout << endl;
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3788kb

input:

1 1
X

output:

0.000000000000000
0
(1,1) 

result:

ok correct!

Test #2:

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

input:

2 1
.X

output:

0.000000000000000
0
(1,1) (2,1) 

result:

ok correct!

Test #3:

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

input:

2 1
X.

output:

0.000000000000000
0
(1,1) (2,1) 

result:

ok correct!

Test #4:

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

input:

1 2
.
X

output:

0.000000000000000
0
(1,1) (1,2) 

result:

ok correct!

Test #5:

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

input:

1 2
X
.

output:

0.000000000000000
0
(1,1) (1,2) 

result:

ok correct!

Test #6:

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

input:

2 1
XX

output:

3.000000000000000
3
(1,1) (2,1) 

result:

ok correct!

Test #7:

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

input:

3 3
XXX
X.X
XXX

output:

3.111111111111111
5
(3,1) (3,2) 

result:

ok correct!

Test #8:

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

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

result:

ok correct!

Test #9:

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

input:

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

output:

19735.319899999998597
39599
(100,1) (100,2) 

result:

ok correct!

Test #10:

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

input:

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

output:

19865.669900000000780
39500
(100,1) (100,2) 

result:

ok correct!

Test #11:

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

input:

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

output:

11855.639199999999619
39302
(100,99) (99,100) 

result:

ok correct!

Test #12:

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

input:

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

output:

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

result:

ok correct!

Test #13:

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

input:

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

output:

50.097945205479455
80
(7,6) (16,6) (20,12) (7,15) (16,15) (7,24) (16,24) (7,33) (16,33) (7,42) (16,42) (19,46) (12,47) (20,47) (7,51) (16,51) (12,56) (19,56) (7,60) (16,60) (20,65) (20,67) (7,69) (16,69) 

result:

ok correct!

Test #14:

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

input:

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

output:

100.711201079622128
742
(1,1) (2,1) 

result:

ok correct!

Test #15:

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

input:

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

output:

494.497881355932179
1503
(56,38) (56,39) 

result:

ok correct!

Test #16:

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

input:

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

output:

122.545311681508650
387
(1,19) (19,32) 

result:

ok correct!

Test #17:

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

input:

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

output:

103.487444100447192
334
(10,57) (11,57) 

result:

ok correct!

Test #18:

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

input:

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

output:

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

result:

ok correct!

Test #19:

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

input:

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

output:

79.149333333333331
319
(1,39) (1,40) 

result:

ok correct!

Test #20:

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

input:

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

output:

383.808323787705206
1084
(93,9) (51,51) 

result:

ok correct!

Test #21:

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

input:

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

output:

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

result:

ok correct!

Test #22:

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

input:

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

output:

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

result:

ok correct!

Test #23:

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

input:

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

output:

291.706029452625728
860
(1,1) (1,50) 

result:

ok correct!

Test #24:

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

input:

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

output:

152.161880630630634
512
(48,9) (48,67) 

result:

ok correct!

Test #25:

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

input:

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

output:

212.396250000000009
1031
(1,67) (1,68) 

result:

ok correct!

Test #26:

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

input:

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

output:

357.121327254305982
2687
(1,83) (1,84) 

result:

ok correct!

Test #27:

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

input:

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

output:

225.855523255813949
975
(84,1) (85,1) 

result:

ok correct!

Test #28:

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

input:

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

output:

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

result:

ok correct!

Test #29:

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

input:

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

output:

738.974479638009029
3378
(5,45) (5,56) 

result:

ok correct!

Test #30:

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

input:

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

output:

1550.390977443609017
4192
(76,34) (76,96) 

result:

ok correct!

Test #31:

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

input:

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

output:

648.650216658642307
2420
(16,1) (1,13) 

result:

ok correct!

Test #32:

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

input:

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

output:

207.337755102040830
895
(1,97) (1,98) 

result:

ok correct!

Test #33:

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

input:

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

output:

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

result:

ok correct!

Test #34:

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

input:

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

output:

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

result:

ok correct!

Test #35:

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

input:

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

output:

142.153824036802774
673
(1,74) (2,74) 

result:

ok correct!

Test #36:

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

input:

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

output:

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

result:

ok correct!

Test #37:

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

input:

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

output:

81.669984917043735
314
(1,64) (1,65) 

result:

ok correct!

Test #38:

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

input:

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

output:

300.307526881720435
1326
(39,93) (40,93) 

result:

ok correct!

Test #39:

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

input:

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

output:

474.068965517241395
2063
(1,1) (49,1) 

result:

ok correct!

Test #40:

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

input:

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

output:

2555.367483811285638
5914
(46,1) (46,2) 

result:

ok correct!

Test #41:

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

input:

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

output:

2389.200358422939189
11288
(21,60) (22,60) 

result:

ok correct!

Test #42:

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

input:

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

output:

225.089160254265636
803
(10,61) (11,61) 

result:

ok correct!

Test #43:

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

input:

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

output:

213.687569988801783
941
(33,89) (33,90) 

result:

ok correct!

Test #44:

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

input:

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

output:

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

result:

ok correct!

Test #45:

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

input:

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

output:

67.354743083003953
645
(1,1) (2,1) 

result:

ok correct!

Test #46:

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

input:

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

output:

80.041025641025641
332
(64,34) (65,34) 

result:

ok correct!

Test #47:

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

input:

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

output:

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

result:

ok correct!

Test #48:

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

input:

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

output:

302.789846743295016
799
(87,29) (87,58) 

result:

ok correct!

Test #49:

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

input:

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

output:

150.346912521440828
930
(52,44) (53,44) 

result:

ok correct!

Test #50:

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

input:

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

output:

690.646413687212089
3826
(1,96) (1,97) 

result:

ok correct!

Test #51:

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

input:

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

output:

356.974579831932772
1620
(23,68) (51,68) 

result:

ok correct!

Test #52:

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

input:

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

output:

1705.102197802197907
4664
(100,44) (100,90) 

result:

ok correct!

Test #53:

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

input:

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

output:

2976.142316017315807
8305
(68,1) (69,1) 

result:

ok correct!

Test #54:

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

input:

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

output:

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

result:

ok correct!

Test #55:

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

input:

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

output:

179.279251700680277
713
(98,56) (98,57) 

result:

ok correct!

Test #56:

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

input:

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

output:

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

result:

ok correct!

Test #57:

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

input:

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

output:

115.940570175438594
390
(15,48) (79,48) 

result:

ok correct!

Test #58:

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

input:

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

output:

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

result:

ok correct!

Test #59:

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

input:

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

output:

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

result:

ok correct!

Test #60:

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

input:

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

output:

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

result:

ok correct!

Test #61:

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

input:

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

output:

164.878078078078090
772
(1,7) (1,8) 

result:

ok correct!

Test #62:

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

input:

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

output:

106.012937595129372
560
(1,1) (1,2) 

result:

ok correct!

Test #63:

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

input:

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

output:

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

result:

ok correct!

Test #64:

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

input:

1 2
X
X

output:

1.000000000000000
1
(1,1) (1,2) 

result:

ok correct!

Test #65:

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

input:

1 3
X
.
.

output:

0.666666666666667
1
(1,1) (1,2) 

result:

ok correct!

Test #66:

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

input:

1 3
.
X
.

output:

0.666666666666667
1
(1,1) (1,3) 

result:

ok correct!

Test #67:

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

input:

1 3
X
X
.

output:

0.666666666666667
1
(1,2) (1,3) 

result:

ok correct!

Test #68:

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

input:

1 3
.
.
X

output:

3.333333333333333
5
(1,2) (1,3) 

result:

ok correct!

Test #69:

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

input:

1 3
X
.
X

output:

6.666666666666667
10
(1,1) (1,3) 

result:

ok correct!

Test #70:

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

input:

1 3
.
X
X

output:

0.666666666666667
1
(1,1) (1,2) 

result:

ok correct!

Test #71:

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

input:

1 3
X
X
X

output:

3.666666666666667
5
(1,1) (1,2) 

result:

ok correct!

Test #72:

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

input:

1 4
X
.
.
.

output:

5.250000000000000
10
(1,1) (1,2) 

result:

ok correct!

Test #73:

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

input:

1 4
.
X
.
.

output:

2.750000000000000
5
(1,1) (1,4) 

result:

ok correct!

Test #74:

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

input:

1 4
X
X
.
.

output:

1.000000000000000
1
(1,1) (1,2) (1,3) (1,4) 

result:

ok correct!

Test #75:

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

input:

1 4
.
.
X
.

output:

2.750000000000000
5
(1,3) (1,4) 

result:

ok correct!

Test #76:

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

input:

1 4
X
.
X
.

output:

7.500000000000000
10
(1,2) (1,4) 

result:

ok correct!

Test #77:

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

input:

1 4
.
X
X
.

output:

1.000000000000000
1
(1,1) (1,2) (1,3) (1,4) 

result:

ok correct!

Test #78:

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

input:

1 4
X
X
X
.

output:

2.750000000000000
5
(1,2) (1,3) 

result:

ok correct!

Test #79:

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

input:

1 4
.
.
.
X

output:

10.250000000000000
18
(1,3) (1,4) 

result:

ok correct!

Test #80:

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

input:

1 4
X
.
.
X

output:

14.000000000000000
27
(1,1) (1,4) 

result:

ok correct!

Test #81:

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

input:

1 4
.
X
.
X

output:

5.500000000000000
10
(1,1) (1,3) 

result:

ok correct!

Test #82:

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

input:

1 4
X
X
.
X

output:

2.750000000000000
5
(1,1) (1,4) 

result:

ok correct!

Test #83:

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

input:

1 4
.
.
X
X

output:

3.000000000000000
5
(1,3) (1,4) 

result:

ok correct!

Test #84:

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

input:

1 4
X
.
X
X

output:

2.750000000000000
5
(1,2) (1,4) 

result:

ok correct!

Test #85:

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

input:

1 4
.
X
X
X

output:

2.750000000000000
5
(1,1) (1,2) 

result:

ok correct!

Test #86:

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

input:

1 4
X
X
X
X

output:

6.500000000000000
10
(1,2) (1,3) 

result:

ok correct!

Test #87:

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

input:

2 2
X.
..

output:

3.750000000000000
7
(2,1) (2,2) 

result:

ok correct!

Test #88:

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

input:

2 2
.X
..

output:

1.250000000000000
2
(1,1) (1,2) 

result:

ok correct!

Test #89:

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

input:

2 2
XX
..

output:

2.500000000000000
3
(1,2) (2,2) 

result:

ok correct!

Test #90:

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

input:

2 2
..
X.

output:

4.250000000000000
6
(2,1) (2,2) 

result:

ok correct!

Test #91:

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

input:

2 2
X.
X.

output:

3.500000000000000
6
(2,1) (2,2) 

result:

ok correct!

Test #92:

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

input:

2 2
.X
X.

output:

1.500000000000000
2
(1,1) (2,2) 

result:

ok correct!

Test #93:

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

input:

2 2
XX
X.

output:

1.750000000000000
3
(1,2) (2,2) 

result:

ok correct!

Test #94:

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

input:

2 2
..
.X

output:

2.750000000000000
4
(1,2) (2,2) 

result:

ok correct!

Test #95:

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

input:

2 2
X.
.X

output:

2.500000000000000
4
(2,1) (1,2) 

result:

ok correct!

Test #96:

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

input:

2 2
.X
.X

output:

1.500000000000000
2
(1,1) (1,2) 

result:

ok correct!

Test #97:

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

input:

2 2
XX
.X

output:

1.750000000000000
3
(1,2) (2,2) 

result:

ok correct!

Test #98:

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

input:

2 2
..
XX

output:

3.500000000000000
4
(1,2) (2,2) 

result:

ok correct!

Test #99:

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

input:

2 2
X.
XX

output:

2.250000000000000
4
(2,1) (1,2) 

result:

ok correct!

Test #100:

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

input:

2 2
.X
XX

output:

1.250000000000000
2
(1,1) (2,2) 

result:

ok correct!

Test #101:

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

input:

2 2
XX
XX

output:

2.500000000000000
3
(1,2) (2,2) 

result:

ok correct!

Test #102:

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

input:

3 1
X..

output:

4.666666666666667
7
(2,1) (3,1) 

result:

ok correct!

Test #103:

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

input:

3 1
.X.

output:

2.000000000000000
3
(1,1) (3,1) 

result:

ok correct!

Test #104:

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

input:

3 1
XX.

output:

2.000000000000000
3
(1,1) (2,1) 

result:

ok correct!

Test #105:

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

input:

3 1
..X

output:

2.000000000000000
3
(1,1) (2,1) 

result:

ok correct!

Test #106:

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

input:

3 1
X.X

output:

9.333333333333334
14
(1,1) (3,1) 

result:

ok correct!

Test #107:

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

input:

3 1
.XX

output:

2.000000000000000
3
(2,1) (3,1) 

result:

ok correct!

Test #108:

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

input:

3 1
XXX

output:

5.666666666666667
7
(1,1) (2,1) 

result:

ok correct!

Test #109:

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

input:

4 1
X...

output:

12.750000000000000
22
(3,1) (4,1) 

result:

ok correct!

Test #110:

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

input:

4 1
.X..

output:

4.250000000000000
7
(3,1) (4,1) 

result:

ok correct!

Test #111:

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

input:

4 1
XX..

output:

5.000000000000000
7
(3,1) (4,1) 

result:

ok correct!

Test #112:

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

input:

4 1
..X.

output:

4.250000000000000
7
(1,1) (4,1) 

result:

ok correct!

Test #113:

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

input:

4 1
X.X.

output:

8.500000000000000
14
(1,1) (3,1) 

result:

ok correct!

Test #114:

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

input:

4 1
.XX.

output:

3.000000000000000
3
(1,1) (2,1) (3,1) (4,1) 

result:

ok correct!

Test #115:

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

input:

4 1
XXX.

output:

4.250000000000000
7
(1,1) (2,1) 

result:

ok correct!

Test #116:

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

input:

4 1
...X

output:

7.750000000000000
14
(1,1) (2,1) 

result:

ok correct!

Test #117:

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

input:

4 1
X..X

output:

18.000000000000000
33
(1,1) (4,1) 

result:

ok correct!

Test #118:

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

input:

4 1
.X.X

output:

10.500000000000000
14
(2,1) (4,1) 

result:

ok correct!

Test #119:

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

input:

4 1
XX.X

output:

4.250000000000000
7
(2,1) (4,1) 

result:

ok correct!

Test #120:

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

input:

4 1
..XX

output:

3.000000000000000
3
(1,1) (2,1) (3,1) (4,1) 

result:

ok correct!

Test #121:

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

input:

4 1
X.XX

output:

4.250000000000000
7
(1,1) (4,1) 

result:

ok correct!

Test #122:

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

input:

4 1
.XXX

output:

4.250000000000000
7
(2,1) (3,1) 

result:

ok correct!

Test #123:

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

input:

4 1
XXXX

output:

9.500000000000000
14
(2,1) (3,1) 

result:

ok correct!

Test #124:

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

input:

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

output:

13274.590000000000146
38710
(99,1) (100,1) 

result:

ok correct!

Test #125:

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

input:

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

output:

13076.629999999999200
38318
(1,1) (2,1) 

result:

ok correct!

Test #126:

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

input:

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

output:

3356.010000000000218
9751
(1,1) (100,1) 

result:

ok correct!

Test #127:

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

input:

100 1
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

output:

3457.500000000000000
9950
(50,1) (51,1) 

result:

ok correct!

Test #128:

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

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

result:

ok correct!

Test #129:

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

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

result:

ok correct!

Test #130:

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

input:

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

output:

12977.649999999999636
38122
(1,1) (1,2) 

result:

ok correct!

Test #131:

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

input:

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

output:

13175.610000000000582
38514
(1,99) (1,100) 

result:

ok correct!

Test #132:

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

input:

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

output:

3306.030000000000200
9653
(1,99) (1,100) 

result:

ok correct!

Test #133:

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

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

result:

ok correct!

Test #134:

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

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

result:

ok correct!

Test #135:

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

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

result:

ok correct!

Test #136:

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

input:

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

output:

58.079999999999998
95
(5,10) (6,10) 

result:

ok correct!

Test #137:

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

input:

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

output:

13878.927499999999782
38908
(99,1) (100,1) 

result:

ok correct!

Test #138:

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

input:

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

output:

14059.272499999999127
39302
(99,100) (100,100) 

result:

ok correct!

Test #139:

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

input:

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

output:

14132.282499999999345
39500
(100,1) (100,2) 

result:

ok correct!

Test #140:

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

input:

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

output:

13951.432500000000800
39104
(1,99) (1,100) 

result:

ok correct!

Test #141:

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

input:

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

output:

19733.339899999999034
39302
(99,100) (100,100) 

result:

ok correct!

Test #142:

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

input:

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

output:

19601.009900000000926
39104
(1,99) (1,100) 

result:

ok correct!

Test #143:

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

input:

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

output:

5001.489899999999579
10098
(99,100) (100,100) 

result:

ok correct!

Test #144:

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

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

result:

ok correct!

Test #145:

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

input:

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

output:

60.830800000000004
195
(28,1) (1,35) 

result:

ok correct!

Test #146:

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

input:

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

output:

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

result:

ok correct!

Extra Test:

score: 0
Extra Test Passed