QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#267288#5112. Where Am I?juampiAC ✓468ms64064kbPython32.2kb2023-11-27 04:42:102023-11-27 04:42:11

Judging History

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

  • [2023-11-27 04:42:11]
  • 评测
  • 测评结果:AC
  • 用时:468ms
  • 内存:64064kb
  • [2023-11-27 04:42:10]
  • 提交

answer

from typing import List
from collections import defaultdict

def main():
    
    X, Y = map(int, input().split())
    g = [input().strip() for _ in range(Y)]
    g.reverse()
    
    dist = [[0] * 201 for _ in range(201)]
    x, y, dx, dy, step, stepn, cur = 100, 100, 0, 1, 0, 1, 0

    while y < 201:
        dist[y][x] = cur
        x += dx
        y += dy
        step += 1
        if step == stepn:
            dx, dy = dy, -dx
            step = 0
            if dy:
                stepn += 1
        cur += 1

    obs = defaultdict(list)

    for y in range(Y):
        for x in range(X):
            if g[y][x] == 'X':
                i = 0
                for sy in range(Y):
                    for sx in range(X):
                        obs[dist[y - sy + 100][x - sx + 100]].append(i)
                        i+=1

    comp = [0] * (X * Y)
    compt = [0] * (X * Y)
    compsz = [X * Y]


    t = 0
    while len(compsz) < X * Y:
        if len(obs[t]) !=0:
            v = obs[t]
            v.sort(key=lambda x: comp[x])
            v.reverse()
            i, j = 0, 0
            while i < len(v):
                j += 1
                while j < len(v) and comp[v[j]] == comp[v[i]]:
                    j += 1
                
                sz = compsz[comp[v[i]]]
                
                if j - i != sz: 
                    if j - i == 1:
                        compt[len(compsz)] = t
                    sz -= j - i
                    compsz[comp[v[i]]] = sz
                    if sz == 1:
                        compt[comp[v[i]]] = t
                    for k in range(i, j):
                        comp[v[k]] = len(compsz)
                    compsz.append(j - i)
                    
                i = j
        t += 1

    
    mx = max(compt)
    tot = sum(compt)

    print(f"{tot / X / Y:.9f}")
    print(mx)

    first = True
    for i in range(X * Y):
        if compt[comp[i]] == mx:
            if not first:
                print(' ', end='')
            first = False
            print(f"({i % X + 1},{i // X + 1})", end='')

    print()


if __name__ == "__main__":
    main()

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 23ms
memory: 10896kb

input:

1 1
X

output:

0.000000000
0
(1,1)

result:

ok correct!

Test #2:

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

input:

2 1
.X

output:

0.000000000
0
(1,1) (2,1)

result:

ok correct!

Test #3:

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

input:

2 1
X.

output:

0.000000000
0
(1,1) (2,1)

result:

ok correct!

Test #4:

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

input:

1 2
.
X

output:

0.000000000
0
(1,1) (1,2)

result:

ok correct!

Test #5:

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

input:

1 2
X
.

output:

0.000000000
0
(1,1) (1,2)

result:

ok correct!

Test #6:

score: 0
Accepted
time: 18ms
memory: 10892kb

input:

2 1
XX

output:

3.000000000
3
(1,1) (2,1)

result:

ok correct!

Test #7:

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

input:

3 3
XXX
X.X
XXX

output:

3.111111111
5
(3,1) (3,2)

result:

ok correct!

Test #8:

score: 0
Accepted
time: 231ms
memory: 48120kb

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

result:

ok correct!

Test #9:

score: 0
Accepted
time: 43ms
memory: 17136kb

input:

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

output:

19735.319900000
39599
(100,1) (100,2)

result:

ok correct!

Test #10:

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

input:

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

output:

19865.669900000
39500
(100,1) (100,2)

result:

ok correct!

Test #11:

score: 0
Accepted
time: 437ms
memory: 58740kb

input:

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

output:

11855.639200000
39302
(100,99) (99,100)

result:

ok correct!

Test #12:

score: 0
Accepted
time: 433ms
memory: 58752kb

input:

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

output:

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

result:

ok correct!

Test #13:

score: 0
Accepted
time: 41ms
memory: 16520kb

input:

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

output:

50.097945205
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: 80ms
memory: 25760kb

input:

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

output:

100.711201080
742
(1,1) (2,1)

result:

ok correct!

Test #15:

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

input:

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

output:

494.497881356
1503
(56,38) (56,39)

result:

ok correct!

Test #16:

score: 0
Accepted
time: 66ms
memory: 23936kb

input:

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

output:

122.545311682
387
(1,19) (19,32)

result:

ok correct!

Test #17:

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

input:

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

output:

103.487444100
334
(10,57) (11,57)

result:

ok correct!

Test #18:

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

input:

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

output:

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

result:

ok correct!

Test #19:

score: 0
Accepted
time: 78ms
memory: 23052kb

input:

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

output:

79.149333333
319
(1,39) (1,40)

result:

ok correct!

Test #20:

score: 0
Accepted
time: 79ms
memory: 26184kb

input:

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

output:

383.808323788
1084
(93,9) (51,51)

result:

ok correct!

Test #21:

score: 0
Accepted
time: 64ms
memory: 23232kb

input:

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

output:

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

result:

ok correct!

Test #22:

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

input:

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

output:

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

result:

ok correct!

Test #23:

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

input:

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

output:

291.706029453
860
(1,1) (1,50)

result:

ok correct!

Test #24:

score: 0
Accepted
time: 51ms
memory: 20480kb

input:

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

output:

152.161880631
512
(48,9) (48,67)

result:

ok correct!

Test #25:

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

input:

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

output:

212.396250000
1031
(1,67) (1,68)

result:

ok correct!

Test #26:

score: 0
Accepted
time: 128ms
memory: 33320kb

input:

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

output:

357.121327254
2687
(1,83) (1,84)

result:

ok correct!

Test #27:

score: 0
Accepted
time: 122ms
memory: 33816kb

input:

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

output:

225.855523256
975
(84,1) (85,1)

result:

ok correct!

Test #28:

score: 0
Accepted
time: 99ms
memory: 28504kb

input:

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

output:

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

result:

ok correct!

Test #29:

score: 0
Accepted
time: 106ms
memory: 24896kb

input:

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

output:

738.974479638
3378
(5,45) (5,56)

result:

ok correct!

Test #30:

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

input:

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

output:

1550.390977444
4192
(76,34) (76,96)

result:

ok correct!

Test #31:

score: 0
Accepted
time: 36ms
memory: 15364kb

input:

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

output:

648.650216659
2420
(16,1) (1,13)

result:

ok correct!

Test #32:

score: 0
Accepted
time: 88ms
memory: 27880kb

input:

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

output:

207.337755102
895
(1,97) (1,98)

result:

ok correct!

Test #33:

score: 0
Accepted
time: 168ms
memory: 42692kb

input:

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

output:

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

result:

ok correct!

Test #34:

score: 0
Accepted
time: 37ms
memory: 14316kb

input:

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

output:

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

result:

ok correct!

Test #35:

score: 0
Accepted
time: 46ms
memory: 20576kb

input:

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

output:

142.153824037
673
(1,74) (2,74)

result:

ok correct!

Test #36:

score: 0
Accepted
time: 59ms
memory: 22484kb

input:

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

output:

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

result:

ok correct!

Test #37:

score: 0
Accepted
time: 77ms
memory: 24820kb

input:

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

output:

81.669984917
314
(1,64) (1,65)

result:

ok correct!

Test #38:

score: 0
Accepted
time: 43ms
memory: 16868kb

input:

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

output:

300.307526882
1326
(39,93) (40,93)

result:

ok correct!

Test #39:

score: 0
Accepted
time: 140ms
memory: 38032kb

input:

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

output:

474.068965517
2063
(1,1) (49,1)

result:

ok correct!

Test #40:

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

input:

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

output:

2555.367483811
5914
(46,1) (46,2)

result:

ok correct!

Test #41:

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

input:

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

output:

2389.200358423
11288
(21,60) (22,60)

result:

ok correct!

Test #42:

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

input:

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

output:

225.089160254
803
(10,61) (11,61)

result:

ok correct!

Test #43:

score: 0
Accepted
time: 182ms
memory: 46624kb

input:

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

output:

213.687569989
941
(33,89) (33,90)

result:

ok correct!

Test #44:

score: 0
Accepted
time: 121ms
memory: 29264kb

input:

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

output:

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

result:

ok correct!

Test #45:

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

input:

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

output:

67.354743083
645
(1,1) (2,1)

result:

ok correct!

Test #46:

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

input:

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

output:

80.041025641
332
(64,34) (65,34)

result:

ok correct!

Test #47:

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

input:

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

output:

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

result:

ok correct!

Test #48:

score: 0
Accepted
time: 68ms
memory: 22240kb

input:

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

output:

302.789846743
799
(87,29) (87,58)

result:

ok correct!

Test #49:

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

input:

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

output:

150.346912521
930
(52,44) (53,44)

result:

ok correct!

Test #50:

score: 0
Accepted
time: 143ms
memory: 33936kb

input:

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

output:

690.646413687
3826
(1,96) (1,97)

result:

ok correct!

Test #51:

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

input:

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

output:

356.974579832
1620
(23,68) (51,68)

result:

ok correct!

Test #52:

score: 0
Accepted
time: 70ms
memory: 21940kb

input:

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

output:

1705.102197802
4664
(100,44) (100,90)

result:

ok correct!

Test #53:

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

input:

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

output:

2976.142316017
8305
(68,1) (69,1)

result:

ok correct!

Test #54:

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

input:

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

output:

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

result:

ok correct!

Test #55:

score: 0
Accepted
time: 142ms
memory: 35132kb

input:

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

output:

179.279251701
713
(98,56) (98,57)

result:

ok correct!

Test #56:

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

input:

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

output:

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

result:

ok correct!

Test #57:

score: 0
Accepted
time: 99ms
memory: 30388kb

input:

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

output:

115.940570175
390
(15,48) (79,48)

result:

ok correct!

Test #58:

score: 0
Accepted
time: 67ms
memory: 20816kb

input:

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

output:

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

result:

ok correct!

Test #59:

score: 0
Accepted
time: 188ms
memory: 45292kb

input:

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

output:

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

result:

ok correct!

Test #60:

score: 0
Accepted
time: 126ms
memory: 34780kb

input:

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

output:

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

result:

ok correct!

Test #61:

score: 0
Accepted
time: 48ms
memory: 18664kb

input:

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

output:

164.878078078
772
(1,7) (1,8)

result:

ok correct!

Test #62:

score: 0
Accepted
time: 83ms
memory: 25440kb

input:

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

output:

106.012937595
560
(1,1) (1,2)

result:

ok correct!

Test #63:

score: 0
Accepted
time: 113ms
memory: 30832kb

input:

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

output:

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

result:

ok correct!

Test #64:

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

input:

1 2
X
X

output:

1.000000000
1
(1,1) (1,2)

result:

ok correct!

Test #65:

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

input:

1 3
X
.
.

output:

0.666666667
1
(1,1) (1,2)

result:

ok correct!

Test #66:

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

input:

1 3
.
X
.

output:

0.666666667
1
(1,1) (1,3)

result:

ok correct!

Test #67:

score: 0
Accepted
time: 18ms
memory: 10896kb

input:

1 3
X
X
.

output:

0.666666667
1
(1,2) (1,3)

result:

ok correct!

Test #68:

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

input:

1 3
.
.
X

output:

3.333333333
5
(1,2) (1,3)

result:

ok correct!

Test #69:

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

input:

1 3
X
.
X

output:

6.666666667
10
(1,1) (1,3)

result:

ok correct!

Test #70:

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

input:

1 3
.
X
X

output:

0.666666667
1
(1,1) (1,2)

result:

ok correct!

Test #71:

score: 0
Accepted
time: 18ms
memory: 10848kb

input:

1 3
X
X
X

output:

3.666666667
5
(1,1) (1,2)

result:

ok correct!

Test #72:

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

input:

1 4
X
.
.
.

output:

5.250000000
10
(1,1) (1,2)

result:

ok correct!

Test #73:

score: 0
Accepted
time: 18ms
memory: 10868kb

input:

1 4
.
X
.
.

output:

2.750000000
5
(1,1) (1,4)

result:

ok correct!

Test #74:

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

input:

1 4
X
X
.
.

output:

1.000000000
1
(1,1) (1,2) (1,3) (1,4)

result:

ok correct!

Test #75:

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

input:

1 4
.
.
X
.

output:

2.750000000
5
(1,3) (1,4)

result:

ok correct!

Test #76:

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

input:

1 4
X
.
X
.

output:

7.500000000
10
(1,2) (1,4)

result:

ok correct!

Test #77:

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

input:

1 4
.
X
X
.

output:

1.000000000
1
(1,1) (1,2) (1,3) (1,4)

result:

ok correct!

Test #78:

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

input:

1 4
X
X
X
.

output:

2.750000000
5
(1,2) (1,3)

result:

ok correct!

Test #79:

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

input:

1 4
.
.
.
X

output:

10.250000000
18
(1,3) (1,4)

result:

ok correct!

Test #80:

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

input:

1 4
X
.
.
X

output:

14.000000000
27
(1,1) (1,4)

result:

ok correct!

Test #81:

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

input:

1 4
.
X
.
X

output:

5.500000000
10
(1,1) (1,3)

result:

ok correct!

Test #82:

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

input:

1 4
X
X
.
X

output:

2.750000000
5
(1,1) (1,4)

result:

ok correct!

Test #83:

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

input:

1 4
.
.
X
X

output:

3.000000000
5
(1,3) (1,4)

result:

ok correct!

Test #84:

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

input:

1 4
X
.
X
X

output:

2.750000000
5
(1,2) (1,4)

result:

ok correct!

Test #85:

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

input:

1 4
.
X
X
X

output:

2.750000000
5
(1,1) (1,2)

result:

ok correct!

Test #86:

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

input:

1 4
X
X
X
X

output:

6.500000000
10
(1,2) (1,3)

result:

ok correct!

Test #87:

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

input:

2 2
X.
..

output:

3.750000000
7
(2,1) (2,2)

result:

ok correct!

Test #88:

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

input:

2 2
.X
..

output:

1.250000000
2
(1,1) (1,2)

result:

ok correct!

Test #89:

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

input:

2 2
XX
..

output:

2.500000000
3
(1,2) (2,2)

result:

ok correct!

Test #90:

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

input:

2 2
..
X.

output:

4.250000000
6
(2,1) (2,2)

result:

ok correct!

Test #91:

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

input:

2 2
X.
X.

output:

3.500000000
6
(2,1) (2,2)

result:

ok correct!

Test #92:

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

input:

2 2
.X
X.

output:

1.500000000
2
(1,1) (2,2)

result:

ok correct!

Test #93:

score: 0
Accepted
time: 18ms
memory: 10852kb

input:

2 2
XX
X.

output:

1.750000000
3
(1,2) (2,2)

result:

ok correct!

Test #94:

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

input:

2 2
..
.X

output:

2.750000000
4
(1,2) (2,2)

result:

ok correct!

Test #95:

score: 0
Accepted
time: 18ms
memory: 10912kb

input:

2 2
X.
.X

output:

2.500000000
4
(2,1) (1,2)

result:

ok correct!

Test #96:

score: 0
Accepted
time: 18ms
memory: 11016kb

input:

2 2
.X
.X

output:

1.500000000
2
(1,1) (1,2)

result:

ok correct!

Test #97:

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

input:

2 2
XX
.X

output:

1.750000000
3
(1,2) (2,2)

result:

ok correct!

Test #98:

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

input:

2 2
..
XX

output:

3.500000000
4
(1,2) (2,2)

result:

ok correct!

Test #99:

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

input:

2 2
X.
XX

output:

2.250000000
4
(2,1) (1,2)

result:

ok correct!

Test #100:

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

input:

2 2
.X
XX

output:

1.250000000
2
(1,1) (2,2)

result:

ok correct!

Test #101:

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

input:

2 2
XX
XX

output:

2.500000000
3
(1,2) (2,2)

result:

ok correct!

Test #102:

score: 0
Accepted
time: 18ms
memory: 10996kb

input:

3 1
X..

output:

4.666666667
7
(2,1) (3,1)

result:

ok correct!

Test #103:

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

input:

3 1
.X.

output:

2.000000000
3
(1,1) (3,1)

result:

ok correct!

Test #104:

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

input:

3 1
XX.

output:

2.000000000
3
(1,1) (2,1)

result:

ok correct!

Test #105:

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

input:

3 1
..X

output:

2.000000000
3
(1,1) (2,1)

result:

ok correct!

Test #106:

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

input:

3 1
X.X

output:

9.333333333
14
(1,1) (3,1)

result:

ok correct!

Test #107:

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

input:

3 1
.XX

output:

2.000000000
3
(2,1) (3,1)

result:

ok correct!

Test #108:

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

input:

3 1
XXX

output:

5.666666667
7
(1,1) (2,1)

result:

ok correct!

Test #109:

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

input:

4 1
X...

output:

12.750000000
22
(3,1) (4,1)

result:

ok correct!

Test #110:

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

input:

4 1
.X..

output:

4.250000000
7
(3,1) (4,1)

result:

ok correct!

Test #111:

score: 0
Accepted
time: 18ms
memory: 10920kb

input:

4 1
XX..

output:

5.000000000
7
(3,1) (4,1)

result:

ok correct!

Test #112:

score: 0
Accepted
time: 18ms
memory: 10996kb

input:

4 1
..X.

output:

4.250000000
7
(1,1) (4,1)

result:

ok correct!

Test #113:

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

input:

4 1
X.X.

output:

8.500000000
14
(1,1) (3,1)

result:

ok correct!

Test #114:

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

input:

4 1
.XX.

output:

3.000000000
3
(1,1) (2,1) (3,1) (4,1)

result:

ok correct!

Test #115:

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

input:

4 1
XXX.

output:

4.250000000
7
(1,1) (2,1)

result:

ok correct!

Test #116:

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

input:

4 1
...X

output:

7.750000000
14
(1,1) (2,1)

result:

ok correct!

Test #117:

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

input:

4 1
X..X

output:

18.000000000
33
(1,1) (4,1)

result:

ok correct!

Test #118:

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

input:

4 1
.X.X

output:

10.500000000
14
(2,1) (4,1)

result:

ok correct!

Test #119:

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

input:

4 1
XX.X

output:

4.250000000
7
(2,1) (4,1)

result:

ok correct!

Test #120:

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

input:

4 1
..XX

output:

3.000000000
3
(1,1) (2,1) (3,1) (4,1)

result:

ok correct!

Test #121:

score: 0
Accepted
time: 18ms
memory: 10908kb

input:

4 1
X.XX

output:

4.250000000
7
(1,1) (4,1)

result:

ok correct!

Test #122:

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

input:

4 1
.XXX

output:

4.250000000
7
(2,1) (3,1)

result:

ok correct!

Test #123:

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

input:

4 1
XXXX

output:

9.500000000
14
(2,1) (3,1)

result:

ok correct!

Test #124:

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

input:

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

output:

13274.590000000
38710
(99,1) (100,1)

result:

ok correct!

Test #125:

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

input:

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

output:

13076.630000000
38318
(1,1) (2,1)

result:

ok correct!

Test #126:

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

input:

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

output:

3356.010000000
9751
(1,1) (100,1)

result:

ok correct!

Test #127:

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

input:

100 1
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

output:

3457.500000000
9950
(50,1) (51,1)

result:

ok correct!

Test #128:

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

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

result:

ok correct!

Test #129:

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

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

result:

ok correct!

Test #130:

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

input:

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

output:

12977.650000000
38122
(1,1) (1,2)

result:

ok correct!

Test #131:

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

input:

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

output:

13175.610000000
38514
(1,99) (1,100)

result:

ok correct!

Test #132:

score: 0
Accepted
time: 18ms
memory: 12432kb

input:

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

output:

3306.030000000
9653
(1,99) (1,100)

result:

ok correct!

Test #133:

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

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

result:

ok correct!

Test #134:

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

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

result:

ok correct!

Test #135:

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

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

result:

ok correct!

Test #136:

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

input:

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

output:

58.080000000
95
(5,10) (6,10)

result:

ok correct!

Test #137:

score: 0
Accepted
time: 465ms
memory: 64064kb

input:

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

output:

13878.927500000
38908
(99,1) (100,1)

result:

ok correct!

Test #138:

score: 0
Accepted
time: 461ms
memory: 63992kb

input:

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

output:

14059.272500000
39302
(99,100) (100,100)

result:

ok correct!

Test #139:

score: 0
Accepted
time: 417ms
memory: 56016kb

input:

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

output:

14132.282500000
39500
(100,1) (100,2)

result:

ok correct!

Test #140:

score: 0
Accepted
time: 468ms
memory: 55920kb

input:

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

output:

13951.432500000
39104
(1,99) (1,100)

result:

ok correct!

Test #141:

score: 0
Accepted
time: 40ms
memory: 17236kb

input:

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

output:

19733.339900000
39302
(99,100) (100,100)

result:

ok correct!

Test #142:

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

input:

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

output:

19601.009900000
39104
(1,99) (1,100)

result:

ok correct!

Test #143:

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

input:

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

output:

5001.489900000
10098
(99,100) (100,100)

result:

ok correct!

Test #144:

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

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

result:

ok correct!

Test #145:

score: 0
Accepted
time: 58ms
memory: 21700kb

input:

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

output:

60.830800000
195
(28,1) (1,35)

result:

ok correct!

Test #146:

score: 0
Accepted
time: 214ms
memory: 55100kb

input:

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

output:

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

result:

ok correct!

Extra Test:

score: 0
Extra Test Passed