QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#69642#5112. Where Am I?ricky0129AC ✓459ms7904kbC++172.9kb2022-12-29 05:48:242022-12-29 05:48:26

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-29 05:48:26]
  • 评测
  • 测评结果:AC
  • 用时:459ms
  • 内存:7904kb
  • [2022-12-29 05:48:24]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vll vector<ll>
#define FOR(i,n) for(int i=0;i<n;i++)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define f first
#define s second

const int MOD = (int)1e9+7;

int r,c;
int cc = 0;
//char G[100][100];
vector<string> G;
bool inside(int i, int j){
    return (i>=0 && i<r && j>=0 && j<c);
}
void turn(pii& dir){
    dir = make_pair(dir.s,-dir.f);
}
vector<int> simulate(int i, int j){
    vector<int> pos; 
    int seen = 0;
    int times = 1;
    int tt = 0;
    int curr = 0;
    pii dir = make_pair(-1,0);
    if(G[i][j]=='X'){
        seen++;
        pos.pb(0);
    }
    int kk = 0;
    while(seen!=cc){
        i+=dir.f; j+=dir.s;
        kk++;
        if(inside(i,j) && G[i][j]=='X'){
            pos.pb(kk);
            seen++;
        }
        curr++;
        if(curr==times){
            turn(dir);
            curr = 0; 
            tt++;
            if(tt==2){
                tt = 0; 
                times++;
            }
        }
    }
    return pos;
}
struct info{
    vi arr;
    pii pos;
    info(){}
    info(vi& a, pii start){
        arr = a; 
        pos = start;
    }
    bool operator< (const info& lhs) const { return arr < lhs.arr; } 
};
int main()
{
    //scanf("%d %d\n",&c,&r);
    cin>>c>>r;
    /*
    FOR(i,r) FOR(j,c){
        scanf("%c",&G[i][j]);
        if(G[i][j]=='X') cc++;

    }
    */
    G.resize(r);
    FOR(i,r) cin>>G[i];
    FOR(i,r) FOR(j,c) if(G[i][j]=='X') cc++;
    vector<info> A;
    FOR(i,r){
        FOR(j,c){
            //simulate until you reach all X's
            vi all = simulate(i,j);
            A.pb(info(all,make_pair(i,j)) );
        }
    }
    sort(A.begin(),A.end());
    int ans = 0;
    ll sum = 0;
    vi ans_m(sz(A),0);
    for(int i=0;i<sz(A)-1;i++){
        int l = sz(A[i].arr);
        int r = sz(A[i+1].arr);
        FOR(j,min(l,r)){
            if(A[i].arr[j]!=A[i+1].arr[j]){
                int val = min(A[i].arr[j],A[i+1].arr[j]);
                ans_m[i] = max(ans_m[i],val);
                ans_m[i+1] = max(ans_m[i+1],val);
                ans = max(ans,val);
                break;
            }
        }
    }
    FOR(i,sz(A)) sum+=ans_m[i];
    double ex = sum/(double)sz(A);
    printf("%.8lf\n%d\n",ex,ans);
    vector<pii> all;
    FOR(i,sz(A)) if(ans_m[i]==ans){
        all.pb(make_pair(A[i].pos.s+1,r-A[i].pos.f));
    }
    sort(all.begin(),all.end(),[](pii& a, pii& b){
        if(a.s==b.s) return a.f<b.f;
        return a.s<b.s;
    });
    FOR(i,sz(all)) printf("(%d,%d) ",all[i].f,all[i].s);
    printf("\n");
    //cout<<ex<<endl;
    //cout<<ans<<endl;

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3780kb

input:

1 1
X

output:

0.00000000
0
(1,1) 

result:

ok correct!

Test #2:

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

input:

2 1
.X

output:

0.00000000
0
(1,1) (2,1) 

result:

ok correct!

Test #3:

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

input:

2 1
X.

output:

0.00000000
0
(1,1) (2,1) 

result:

ok correct!

Test #4:

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

input:

1 2
.
X

output:

0.00000000
0
(1,1) (1,2) 

result:

ok correct!

Test #5:

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

input:

1 2
X
.

output:

0.00000000
0
(1,1) (1,2) 

result:

ok correct!

Test #6:

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

input:

2 1
XX

output:

3.00000000
3
(1,1) (2,1) 

result:

ok correct!

Test #7:

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

input:

3 3
XXX
X.X
XXX

output:

3.11111111
5
(3,1) (3,2) 

result:

ok correct!

Test #8:

score: 0
Accepted
time: 451ms
memory: 7036kb

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

result:

ok correct!

Test #9:

score: 0
Accepted
time: 312ms
memory: 3860kb

input:

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

output:

19735.31990000
39599
(100,1) (100,2) 

result:

ok correct!

Test #10:

score: 0
Accepted
time: 309ms
memory: 4152kb

input:

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

output:

19865.66990000
39500
(100,1) (100,2) 

result:

ok correct!

Test #11:

score: 0
Accepted
time: 459ms
memory: 7652kb

input:

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

output:

11855.63920000
39302
(100,99) (99,100) 

result:

ok correct!

Test #12:

score: 0
Accepted
time: 458ms
memory: 7904kb

input:

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

output:

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

result:

ok correct!

Test #13:

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

input:

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

output:

50.09794521
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: 72ms
memory: 5052kb

input:

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

output:

100.71120108
742
(1,1) (2,1) 

result:

ok correct!

Test #15:

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

input:

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

output:

494.49788136
1503
(56,38) (56,39) 

result:

ok correct!

Test #16:

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

input:

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

output:

122.54531168
387
(1,19) (19,32) 

result:

ok correct!

Test #17:

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

input:

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

output:

103.48744410
334
(10,57) (11,57) 

result:

ok correct!

Test #18:

score: 0
Accepted
time: 169ms
memory: 4468kb

input:

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

output:

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

result:

ok correct!

Test #19:

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

input:

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

output:

79.14933333
319
(1,39) (1,40) 

result:

ok correct!

Test #20:

score: 0
Accepted
time: 158ms
memory: 4912kb

input:

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

output:

383.80832379
1084
(93,9) (51,51) 

result:

ok correct!

Test #21:

score: 0
Accepted
time: 130ms
memory: 4580kb

input:

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

output:

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

result:

ok correct!

Test #22:

score: 0
Accepted
time: 104ms
memory: 4692kb

input:

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

output:

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

result:

ok correct!

Test #23:

score: 0
Accepted
time: 63ms
memory: 4004kb

input:

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

output:

291.70602945
860
(1,1) (1,50) 

result:

ok correct!

Test #24:

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

input:

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

output:

152.16188063
512
(48,9) (48,67) 

result:

ok correct!

Test #25:

score: 0
Accepted
time: 419ms
memory: 7648kb

input:

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

output:

212.39625000
1031
(1,67) (1,68) 

result:

ok correct!

Test #26:

score: 0
Accepted
time: 279ms
memory: 5484kb

input:

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

output:

357.12132725
2687
(1,83) (1,84) 

result:

ok correct!

Test #27:

score: 0
Accepted
time: 222ms
memory: 5556kb

input:

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

output:

225.85552326
975
(84,1) (85,1) 

result:

ok correct!

Test #28:

score: 0
Accepted
time: 115ms
memory: 5208kb

input:

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

output:

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

result:

ok correct!

Test #29:

score: 0
Accepted
time: 138ms
memory: 4676kb

input:

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

output:

738.97447964
3378
(5,45) (5,56) 

result:

ok correct!

Test #30:

score: 0
Accepted
time: 249ms
memory: 3860kb

input:

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

output:

1550.39097744
4192
(76,34) (76,96) 

result:

ok correct!

Test #31:

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

input:

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

output:

648.65021666
2420
(16,1) (1,13) 

result:

ok correct!

Test #32:

score: 0
Accepted
time: 175ms
memory: 5312kb

input:

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

output:

207.33775510
895
(1,97) (1,98) 

result:

ok correct!

Test #33:

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

input:

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

output:

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

result:

ok correct!

Test #34:

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

input:

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

output:

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

result:

ok correct!

Test #35:

score: 0
Accepted
time: 63ms
memory: 4528kb

input:

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

output:

142.15382404
673
(1,74) (2,74) 

result:

ok correct!

Test #36:

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

input:

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

output:

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

result:

ok correct!

Test #37:

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

input:

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

output:

81.66998492
314
(1,64) (1,65) 

result:

ok correct!

Test #38:

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

input:

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

output:

300.30752688
1326
(39,93) (40,93) 

result:

ok correct!

Test #39:

score: 0
Accepted
time: 268ms
memory: 5948kb

input:

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

output:

474.06896552
2063
(1,1) (49,1) 

result:

ok correct!

Test #40:

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

input:

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

output:

2555.36748381
5914
(46,1) (46,2) 

result:

ok correct!

Test #41:

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

input:

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

output:

2389.20035842
11288
(21,60) (22,60) 

result:

ok correct!

Test #42:

score: 0
Accepted
time: 204ms
memory: 5176kb

input:

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

output:

225.08916025
803
(10,61) (11,61) 

result:

ok correct!

Test #43:

score: 0
Accepted
time: 358ms
memory: 6956kb

input:

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

output:

213.68756999
941
(33,89) (33,90) 

result:

ok correct!

Test #44:

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

input:

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

output:

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

result:

ok correct!

Test #45:

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

input:

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

output:

67.35474308
645
(1,1) (2,1) 

result:

ok correct!

Test #46:

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

input:

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

output:

80.04102564
332
(64,34) (65,34) 

result:

ok correct!

Test #47:

score: 0
Accepted
time: 110ms
memory: 5252kb

input:

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

output:

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

result:

ok correct!

Test #48:

score: 0
Accepted
time: 144ms
memory: 4544kb

input:

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

output:

302.78984674
799
(87,29) (87,58) 

result:

ok correct!

Test #49:

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

input:

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

output:

150.34691252
930
(52,44) (53,44) 

result:

ok correct!

Test #50:

score: 0
Accepted
time: 360ms
memory: 5840kb

input:

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

output:

690.64641369
3826
(1,96) (1,97) 

result:

ok correct!

Test #51:

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

input:

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

output:

356.97457983
1620
(23,68) (51,68) 

result:

ok correct!

Test #52:

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

input:

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

output:

1705.10219780
4664
(100,44) (100,90) 

result:

ok correct!

Test #53:

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

input:

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

output:

2976.14231602
8305
(68,1) (69,1) 

result:

ok correct!

Test #54:

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

input:

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

output:

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

result:

ok correct!

Test #55:

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

input:

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

output:

179.27925170
713
(98,56) (98,57) 

result:

ok correct!

Test #56:

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

input:

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

output:

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

result:

ok correct!

Test #57:

score: 0
Accepted
time: 145ms
memory: 5560kb

input:

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

output:

115.94057018
390
(15,48) (79,48) 

result:

ok correct!

Test #58:

score: 0
Accepted
time: 54ms
memory: 4700kb

input:

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

output:

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

result:

ok correct!

Test #59:

score: 0
Accepted
time: 336ms
memory: 7000kb

input:

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

output:

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

result:

ok correct!

Test #60:

score: 0
Accepted
time: 320ms
memory: 5844kb

input:

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

output:

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

result:

ok correct!

Test #61:

score: 0
Accepted
time: 72ms
memory: 4396kb

input:

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

output:

164.87807808
772
(1,7) (1,8) 

result:

ok correct!

Test #62:

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

input:

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

output:

106.01293760
560
(1,1) (1,2) 

result:

ok correct!

Test #63:

score: 0
Accepted
time: 159ms
memory: 5616kb

input:

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

output:

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

result:

ok correct!

Test #64:

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

input:

1 2
X
X

output:

1.00000000
1
(1,1) (1,2) 

result:

ok correct!

Test #65:

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

input:

1 3
X
.
.

output:

0.66666667
1
(1,1) (1,2) 

result:

ok correct!

Test #66:

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

input:

1 3
.
X
.

output:

0.66666667
1
(1,1) (1,3) 

result:

ok correct!

Test #67:

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

input:

1 3
X
X
.

output:

0.66666667
1
(1,2) (1,3) 

result:

ok correct!

Test #68:

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

input:

1 3
.
.
X

output:

3.33333333
5
(1,2) (1,3) 

result:

ok correct!

Test #69:

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

input:

1 3
X
.
X

output:

6.66666667
10
(1,1) (1,3) 

result:

ok correct!

Test #70:

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

input:

1 3
.
X
X

output:

0.66666667
1
(1,1) (1,2) 

result:

ok correct!

Test #71:

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

input:

1 3
X
X
X

output:

3.66666667
5
(1,1) (1,2) 

result:

ok correct!

Test #72:

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

input:

1 4
X
.
.
.

output:

5.25000000
10
(1,1) (1,2) 

result:

ok correct!

Test #73:

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

input:

1 4
.
X
.
.

output:

2.75000000
5
(1,1) (1,4) 

result:

ok correct!

Test #74:

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

input:

1 4
X
X
.
.

output:

1.00000000
1
(1,1) (1,2) (1,3) (1,4) 

result:

ok correct!

Test #75:

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

input:

1 4
.
.
X
.

output:

2.75000000
5
(1,3) (1,4) 

result:

ok correct!

Test #76:

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

input:

1 4
X
.
X
.

output:

7.50000000
10
(1,2) (1,4) 

result:

ok correct!

Test #77:

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

input:

1 4
.
X
X
.

output:

1.00000000
1
(1,1) (1,2) (1,3) (1,4) 

result:

ok correct!

Test #78:

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

input:

1 4
X
X
X
.

output:

2.75000000
5
(1,2) (1,3) 

result:

ok correct!

Test #79:

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

input:

1 4
.
.
.
X

output:

10.25000000
18
(1,3) (1,4) 

result:

ok correct!

Test #80:

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

input:

1 4
X
.
.
X

output:

14.00000000
27
(1,1) (1,4) 

result:

ok correct!

Test #81:

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

input:

1 4
.
X
.
X

output:

5.50000000
10
(1,1) (1,3) 

result:

ok correct!

Test #82:

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

input:

1 4
X
X
.
X

output:

2.75000000
5
(1,1) (1,4) 

result:

ok correct!

Test #83:

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

input:

1 4
.
.
X
X

output:

3.00000000
5
(1,3) (1,4) 

result:

ok correct!

Test #84:

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

input:

1 4
X
.
X
X

output:

2.75000000
5
(1,2) (1,4) 

result:

ok correct!

Test #85:

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

input:

1 4
.
X
X
X

output:

2.75000000
5
(1,1) (1,2) 

result:

ok correct!

Test #86:

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

input:

1 4
X
X
X
X

output:

6.50000000
10
(1,2) (1,3) 

result:

ok correct!

Test #87:

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

input:

2 2
X.
..

output:

3.75000000
7
(2,1) (2,2) 

result:

ok correct!

Test #88:

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

input:

2 2
.X
..

output:

1.25000000
2
(1,1) (1,2) 

result:

ok correct!

Test #89:

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

input:

2 2
XX
..

output:

2.50000000
3
(1,2) (2,2) 

result:

ok correct!

Test #90:

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

input:

2 2
..
X.

output:

4.25000000
6
(2,1) (2,2) 

result:

ok correct!

Test #91:

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

input:

2 2
X.
X.

output:

3.50000000
6
(2,1) (2,2) 

result:

ok correct!

Test #92:

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

input:

2 2
.X
X.

output:

1.50000000
2
(1,1) (2,2) 

result:

ok correct!

Test #93:

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

input:

2 2
XX
X.

output:

1.75000000
3
(1,2) (2,2) 

result:

ok correct!

Test #94:

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

input:

2 2
..
.X

output:

2.75000000
4
(1,2) (2,2) 

result:

ok correct!

Test #95:

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

input:

2 2
X.
.X

output:

2.50000000
4
(2,1) (1,2) 

result:

ok correct!

Test #96:

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

input:

2 2
.X
.X

output:

1.50000000
2
(1,1) (1,2) 

result:

ok correct!

Test #97:

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

input:

2 2
XX
.X

output:

1.75000000
3
(1,2) (2,2) 

result:

ok correct!

Test #98:

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

input:

2 2
..
XX

output:

3.50000000
4
(1,2) (2,2) 

result:

ok correct!

Test #99:

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

input:

2 2
X.
XX

output:

2.25000000
4
(2,1) (1,2) 

result:

ok correct!

Test #100:

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

input:

2 2
.X
XX

output:

1.25000000
2
(1,1) (2,2) 

result:

ok correct!

Test #101:

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

input:

2 2
XX
XX

output:

2.50000000
3
(1,2) (2,2) 

result:

ok correct!

Test #102:

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

input:

3 1
X..

output:

4.66666667
7
(2,1) (3,1) 

result:

ok correct!

Test #103:

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

input:

3 1
.X.

output:

2.00000000
3
(1,1) (3,1) 

result:

ok correct!

Test #104:

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

input:

3 1
XX.

output:

2.00000000
3
(1,1) (2,1) 

result:

ok correct!

Test #105:

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

input:

3 1
..X

output:

2.00000000
3
(1,1) (2,1) 

result:

ok correct!

Test #106:

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

input:

3 1
X.X

output:

9.33333333
14
(1,1) (3,1) 

result:

ok correct!

Test #107:

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

input:

3 1
.XX

output:

2.00000000
3
(2,1) (3,1) 

result:

ok correct!

Test #108:

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

input:

3 1
XXX

output:

5.66666667
7
(1,1) (2,1) 

result:

ok correct!

Test #109:

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

input:

4 1
X...

output:

12.75000000
22
(3,1) (4,1) 

result:

ok correct!

Test #110:

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

input:

4 1
.X..

output:

4.25000000
7
(3,1) (4,1) 

result:

ok correct!

Test #111:

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

input:

4 1
XX..

output:

5.00000000
7
(3,1) (4,1) 

result:

ok correct!

Test #112:

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

input:

4 1
..X.

output:

4.25000000
7
(1,1) (4,1) 

result:

ok correct!

Test #113:

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

input:

4 1
X.X.

output:

8.50000000
14
(1,1) (3,1) 

result:

ok correct!

Test #114:

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

input:

4 1
.XX.

output:

3.00000000
3
(1,1) (2,1) (3,1) (4,1) 

result:

ok correct!

Test #115:

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

input:

4 1
XXX.

output:

4.25000000
7
(1,1) (2,1) 

result:

ok correct!

Test #116:

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

input:

4 1
...X

output:

7.75000000
14
(1,1) (2,1) 

result:

ok correct!

Test #117:

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

input:

4 1
X..X

output:

18.00000000
33
(1,1) (4,1) 

result:

ok correct!

Test #118:

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

input:

4 1
.X.X

output:

10.50000000
14
(2,1) (4,1) 

result:

ok correct!

Test #119:

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

input:

4 1
XX.X

output:

4.25000000
7
(2,1) (4,1) 

result:

ok correct!

Test #120:

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

input:

4 1
..XX

output:

3.00000000
3
(1,1) (2,1) (3,1) (4,1) 

result:

ok correct!

Test #121:

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

input:

4 1
X.XX

output:

4.25000000
7
(1,1) (4,1) 

result:

ok correct!

Test #122:

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

input:

4 1
.XXX

output:

4.25000000
7
(2,1) (3,1) 

result:

ok correct!

Test #123:

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

input:

4 1
XXXX

output:

9.50000000
14
(2,1) (3,1) 

result:

ok correct!

Test #124:

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

input:

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

output:

13274.59000000
38710
(99,1) (100,1) 

result:

ok correct!

Test #125:

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

input:

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

output:

13076.63000000
38318
(1,1) (2,1) 

result:

ok correct!

Test #126:

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

input:

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

output:

3356.01000000
9751
(1,1) (100,1) 

result:

ok correct!

Test #127:

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

input:

100 1
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

output:

3457.50000000
9950
(50,1) (51,1) 

result:

ok correct!

Test #128:

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

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

result:

ok correct!

Test #129:

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

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

result:

ok correct!

Test #130:

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

input:

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

output:

12977.65000000
38122
(1,1) (1,2) 

result:

ok correct!

Test #131:

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

input:

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

output:

13175.61000000
38514
(1,99) (1,100) 

result:

ok correct!

Test #132:

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

input:

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

output:

3306.03000000
9653
(1,99) (1,100) 

result:

ok correct!

Test #133:

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

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

result:

ok correct!

Test #134:

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

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

result:

ok correct!

Test #135:

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

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

result:

ok correct!

Test #136:

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

input:

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

output:

58.08000000
95
(5,10) (6,10) 

result:

ok correct!

Test #137:

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

input:

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

output:

13878.92750000
38908
(99,1) (100,1) 

result:

ok correct!

Test #138:

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

input:

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

output:

14059.27250000
39302
(99,100) (100,100) 

result:

ok correct!

Test #139:

score: 0
Accepted
time: 420ms
memory: 7612kb

input:

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

output:

14132.28250000
39500
(100,1) (100,2) 

result:

ok correct!

Test #140:

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

input:

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

output:

13951.43250000
39104
(1,99) (1,100) 

result:

ok correct!

Test #141:

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

input:

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

output:

19733.33990000
39302
(99,100) (100,100) 

result:

ok correct!

Test #142:

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

input:

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

output:

19601.00990000
39104
(1,99) (1,100) 

result:

ok correct!

Test #143:

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

input:

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

output:

5001.48990000
10098
(99,100) (100,100) 

result:

ok correct!

Test #144:

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

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

result:

ok correct!

Test #145:

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

input:

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

output:

60.83080000
195
(28,1) (1,35) 

result:

ok correct!

Test #146:

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

input:

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

output:

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

result:

ok correct!

Extra Test:

score: 0
Extra Test Passed