QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#96273#5153. Delft DistanceRoomGamadan#AC ✓269ms53152kbC++205.1kb2023-04-13 18:21:522023-04-13 18:21:53

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-13 18:21:53]
  • 评测
  • 测评结果:AC
  • 用时:269ms
  • 内存:53152kb
  • [2023-04-13 18:21:52]
  • 提交

answer

#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")

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

#define el '\n'
#define F first
#define S second

typedef long long ll;
typedef long double ld;

bool multipleTestCases = 0, sublime = 0;
const int N = 2e3 + 5, INF = 1e9 + 5, mod = 1e9 + 7, LOG = 22, SQ = 500;

int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

int n, m;
char a[N][N];
ld dist[N][N];

const ld pi = acos(-1) / 2;

bool valid(int i, int j) {
    return i >= 0 and i <= n and j >= 0 and j <= m;
}

ld dijk() {
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            dist[i][j] = 2e9;
        }
    }

    priority_queue<pair<ld, pair<int, int>>> q;
    q.push({0, {0, 0}});
    dist[0][0] = 0;

    while (q.size()) {
        ld d = -q.top().F;
        int i = q.top().S.F, j = q.top().S.S;
        q.pop();

        if (fabs(d - dist[i][j]) > 1e-6) {
            continue;
        }

        if (i % 2 == 0 and j % 2 == 0) {
            for (int k = 0; k < 4; k++) {
                int ni = i + dx[k], nj = j + dy[k];

                if (valid(ni, nj) and dist[ni][nj] > dist[i][j] + 5) {
                    dist[ni][nj] = dist[i][j] + 5;
                    q.push({-dist[ni][nj], {ni, nj}});
                }
            }
        }
        else if (i % 2 == 0 and j % 2 == 1) {
            if (valid(i, j + 1) and dist[i][j + 1] > dist[i][j] + 5) {
                dist[i][j + 1] = dist[i][j] + 5;
                q.push({-dist[i][j + 1], {i, j + 1}});
            }
            if (valid(i, j - 1) and dist[i][j - 1] > dist[i][j] + 5) {
                dist[i][j - 1] = dist[i][j] + 5;
                q.push({-dist[i][j - 1], {i, j - 1}});
            }

            if (i > 0 and a[i / 2 - 1][j / 2] == 'O') {
                // i - 1, j - 1
                if (valid(i - 1, j - 1) and dist[i - 1][j - 1] > dist[i][j] + 5 * pi) {
                    dist[i - 1][j - 1] = dist[i][j] + 5 * pi;
                    q.push({-dist[i - 1][j - 1], {i - 1, j - 1}});
                }
                // i - 1, j + 1
                if (valid(i - 1, j + 1) and dist[i - 1][j + 1] > dist[i][j] + 5 * pi) {
                    dist[i - 1][j + 1] = dist[i][j] + 5 * pi;
                    q.push({-dist[i - 1][j + 1], {i - 1, j + 1}});
                }
            }
            if (i < n and a[i / 2][j / 2] == 'O') {
                // i + 1, j - 1
                if (valid(i + 1, j - 1) and dist[i + 1][j - 1] > dist[i][j] + 5 * pi) {
                    dist[i + 1][j - 1] = dist[i][j] + 5 * pi;
                    q.push({-dist[i + 1][j - 1], {i + 1, j - 1}});
                }
                // i + 1, j + 1
                if (valid(i + 1, j + 1) and dist[i + 1][j + 1] > dist[i][j] + 5 * pi) {
                    dist[i + 1][j + 1] = dist[i][j] + 5 * pi;
                    q.push({-dist[i + 1][j + 1], {i + 1, j + 1}});
                }
            }
        }
        else if (i % 2 == 1 and j % 2 == 0) {
            if (valid(i + 1, j) and dist[i + 1][j] > dist[i][j] + 5) {
                dist[i + 1][j] = dist[i][j] + 5;
                q.push({-dist[i + 1][j], {i + 1, j}});
            }

            if (j > 0 and a[i / 2][j / 2 - 1] == 'O') {
                // i - 1, j - 1
                if (valid(i - 1, j - 1) and dist[i - 1][j - 1] > dist[i][j] + 5 * pi) {
                    dist[i - 1][j - 1] = dist[i][j] + 5 * pi;
                    q.push({-dist[i - 1][j - 1], {i - 1, j - 1}});
                }
                // i + 1, j - 1
                if (valid(i + 1, j - 1) and dist[i + 1][j - 1] > dist[i][j] + 5 * pi) {
                    dist[i + 1][j - 1] = dist[i][j] + 5 * pi;
                    q.push({-dist[i + 1][j - 1], {i + 1, j - 1}});
                }
            }
            if (j < m and a[i / 2][j / 2] == 'O') {
                // i - 1, j + 1
                if (valid(i - 1, j + 1) and dist[i - 1][j + 1] > dist[i][j] + 5 * pi) {
                    dist[i - 1][j + 1] = dist[i][j] + 5 * pi;
                    q.push({-dist[i - 1][j + 1], {i - 1, j + 1}});
                }
                // i + 1, j + 1
                if (valid(i + 1, j + 1) and dist[i + 1][j + 1] > dist[i][j] + 5 * pi) {
                    dist[i + 1][j + 1] = dist[i][j] + 5 * pi;
                    q.push({-dist[i + 1][j + 1], {i + 1, j + 1}});
                }
            }
        }
    }

    return dist[n][m];
}

void doWork() {
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    n = 2 * n;
    m = 2 * m;

    cout << fixed << setprecision(12) << dijk() << el;
}

signed main() {
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#endif
#ifndef ONLINE_JUDGE
    if (sublime) {
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    }
#endif
    int tests = 1;
    if (multipleTestCases) {
        cin >> tests;
    }
    for (int tc = 1; tc <= tests; tc++) {
        doWork();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 5800kb

input:

3 5
XOOXO
OXOXO
XXXXO

output:

71.415926535898

result:

ok found '71.4159265', expected '71.4159265', error '0.0000000'

Test #2:

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

input:

1 4
XOOX

output:

45.707963267949

result:

ok found '45.7079633', expected '45.7079633', error '0.0000000'

Test #3:

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

input:

1 1
X

output:

20.000000000000

result:

ok found '20.0000000', expected '20.0000000', error '0.0000000'

Test #4:

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

input:

1 1
O

output:

17.853981633974

result:

ok found '17.8539816', expected '17.8539816', error '0.0000000'

Test #5:

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

input:

1 3
XOO

output:

35.707963267949

result:

ok found '35.7079633', expected '35.7079633', error '0.0000000'

Test #6:

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

input:

1 5
OXOOO

output:

55.707963267949

result:

ok found '55.7079633', expected '55.7079633', error '0.0000000'

Test #7:

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

input:

6 10
XXXXXOOOOX
XXOOOOOOOO
XXXOXOOXOX
OXOXOXXOOX
OOXXOXXXXO
OXOXXOOXOO

output:

142.831853071796

result:

ok found '142.8318531', expected '142.8318531', error '0.0000000'

Test #8:

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

input:

1 2
XX

output:

30.000000000000

result:

ok found '30.0000000', expected '30.0000000', error '0.0000000'

Test #9:

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

input:

10 1
X
X
X
O
O
O
X
O
O
X

output:

105.707963267949

result:

ok found '105.7079633', expected '105.7079633', error '0.0000000'

Test #10:

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

input:

18 6
OOOOOO
OOOOOO
XOOOOO
OOOOXO
OOOXOO
OOOOOO
OOOOOO
OOOOOO
OOOOOX
OOOOOO
OOOXOO
OOOOOO
OOOOOO
OOOOOO
OOOOOO
OOOOOO
OOOOOO
OOOOOO

output:

214.247779607694

result:

ok found '214.2477796', expected '214.2477796', error '0.0000000'

Test #11:

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

input:

40 9
OOOOXOXXX
XOXXXOXXO
OXOXXXXXO
OXOXXXOXX
XXXXOXOXX
XXOOXOXXX
XOOXOXXXX
XOXXOOXOX
OXXOOOOXX
XXOOOXXOO
OXOOXOXXX
OOOOOXOOO
OXXXXXXXO
OOOOOOOXX
OOOXXXOOX
OXOXXOOOO
OOOOXOXOO
OXOXOOOXO
OXXOOXXXO
OXOOXOOXO
XXXOXOXOO
XXOOOXOOX
OOXXOOXOO
XOOXXXXOX
OXXXXOOOO
OXOOOOXOX
XXOXXXOOO
OOXOOOXXX
OXOOOOXOO
OXOOO...

output:

453.517687777566

result:

ok found '453.5176878', expected '453.5176878', error '0.0000000'

Test #12:

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

input:

41 50
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXO
XXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXOXXXXXXXXXXXXXXX
XXXXXXXXXXXXXOXXXXXXXXXXXXXXOXXXXXXXXXX...

output:

873.517687777566

result:

ok found '873.5176878', expected '873.5176878', error '0.0000000'

Test #13:

score: 0
Accepted
time: 61ms
memory: 26872kb

input:

329 527
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

8560.000000000000

result:

ok found '8560.0000000', expected '8560.0000000', error '0.0000000'

Test #14:

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

input:

49 297
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

3451.415926535898

result:

ok found '3451.4159265', expected '3451.4159265', error '0.0000000'

Test #15:

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

input:

357 83
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

4342.057504117311

result:

ok found '4342.0575041', expected '4342.0575041', error '0.0000000'

Test #16:

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

input:

417 615
XXXXXXXXOXXXXXXXXXXXOXXXXXXXXXXXOXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXOXXXXXXXXXXXXXXOXXXXXOXXXOOXXXXXXXXXXXXXXXXXXXXXOXOXXOXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXOXXXXXXOXXXXXXXXOXXXXXXXOXXXXXXXXXXXXXXXXOXXXXXXOXXXXXXXOXXXXXXXXXXOXXXXXXXXOXXXOXXXOXXXXXOXXXOXXXXXXXXXOXXXXXXXXXXXXXXXXXXXX...

output:

9736.283004441059

result:

ok found '9736.2830044', expected '9736.2830044', error '0.0000000'

Test #17:

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

input:

359 225
OOOOXXOOXOXXXOOOOOXOXOOOXOOXXXXXOOOXOXXXOOOOXXOXXOOXOXOXXOXOXXXOXXXXXOOOXXXXXXXOOOOXXXXXOOXOXXOXOXOXXOXOXXOXOXOOOXOXXXOOXOXOXXXXOXOOXXOXXOXOXOXXOXXXOOOXXOOOXXOXXXXXOXOXOOXXOOXOXXOXXOOOOOXOXOOXXXOOXOOXOOOOXOXOOXXOOOXOOOXXXXOXX
OXOOOXXXOOXOOXOOXXOOXXOOXXOXXOOOOOXOXXOOXXXOXXXOXOOOXOOXXOOXOXXOXO...

output:

5026.659039276329

result:

ok found '5026.6590393', expected '5026.6590393', error '0.0000000'

Test #18:

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

input:

261 431
OOOOOOOXOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOOXOOOOOOXOOOXXOOOOOOOOOOOOOOXOOXOOOOOOXOOOOOOOOOXOOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOXOXOOOOOOOOOOOOOXOOOXOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOOOOXOOOOOOOOOXXOOXOOOOOOOOOOOXOOXOOOOXOXXOOOOOOOOOOXOXOOOOOOOOOOOOOXOOOOOOOOOOOOOXOOOOOOOOXOOOOOOOOOOO...

output:

5799.778412934680

result:

ok found '5799.7784129', expected '5799.7784129', error '0.0000000'

Test #19:

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

input:

37 427
OOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

4481.194640914112

result:

ok found '4481.1946409', expected '4481.1946409', error '0.0000000'

Test #20:

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

input:

105 430
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

4899.336143134641

result:

ok found '4899.3361431', expected '4899.3361431', error '0.0000000'

Test #21:

score: 0
Accepted
time: 108ms
memory: 34976kb

input:

465 484
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

7494.202919596269

result:

ok found '7494.2029196', expected '7494.2029196', error '0.0000000'

Test #22:

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

input:

266 8
OXOOXXOX
OOXOXXXX
XXXXOXXX
XXOOOOXX
XXOXXXOO
OXOXXOXO
XXOXOXXO
OOOXOXOO
OXOXOXOO
XOOXOOXX
XXOXOXXO
OXOOOOXO
XXOOXOOO
OXOOXXXX
XOOOXOXO
XOXOOXOX
OOXOOXOX
XXOOOXXO
XOOXXOXX
XOXOXOXX
OXOOOOOO
XOOXOXOX
OXXXOOXX
XXXOOXOO
XOOOXXOO
OXXXXXXO
OXOXXOOX
OXXOXXOX
OXOXOOXO
XXXOXOOO
OXOXOOXO
OXXXOXXX
XXXXOX...

output:

2705.663706143592

result:

ok found '2705.6637061', expected '2705.6637061', error '0.0000000'

Test #23:

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

input:

366 8
XXXXXXXO
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXOX
XXXXOXXX
XOXXXXXO
XXXXOXXX
OXXXXOXX
XXXXXXXX
XXXXXXXX
OXXXXXXX
XXXXXXXX
XXXOXXXX
XXOXXXXX
XXXOXXOX
XXXOXXXX
XXXXOXXX
XXXXXXXX
XXXXXXOO
XXXXXXXX
XXXXXXXX
XXXXOXXX
XXXXXXXX
XOXXXXXX
XXXXXXXX
XXXXXXXX
XOXXXOXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXX...

output:

3712.101761241668

result:

ok found '3712.1017612', expected '3712.1017612', error '0.0000000'

Test #24:

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

input:

56 2
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XO
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX

output:

577.853981633974

result:

ok found '577.8539816', expected '577.8539816', error '0.0000000'

Test #25:

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

input:

437 2
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
OX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
XX
...

output:

4385.707963267949

result:

ok found '4385.7079633', expected '4385.7079633', error '0.0000000'

Test #26:

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

input:

4 204
OXOOXXXOOOXOOXXOXOXXXXOXXXXOXXXOXXOXXOXOOXOOOOXXXOXOXXXOXOOOOOXOXXXOOXOXXXXOXOOXXXOXOXOXXXOXOXXOOOXOOOXOXXXOXOOXXOOXOOOOOXOOOOOOXOXOXXOOOXXXXOOOXOOOXOOOOXXOXXOOXOXXOXOOXOOXXXOOXXOOXXXXOOOXOXXXXOOXXOOOOXXO
OXXXXXOOXOOXOXOOXOXOOOOXXOXOOOOOXOOOXOOOXOXXXOXXOXXXOOXOOXXXXXOXOXXXXXXOOXXOXXXXXOXOXOOXO...

output:

2062.831853071796

result:

ok found '2062.8318531', expected '2062.8318531', error '0.0000000'

Test #27:

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

input:

4 164
XXXXXXXXXXXXOXXXXOXXXXXXXXXXXXXXXXXXXXXXOXOXOOXOXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXOXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXOXXXXXXXXXXXXXXXXOXXXO
XXXOXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXOXXXXXXXXXXXXOOXXXXXXOXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXOXXX...

output:

1662.831853071796

result:

ok found '1662.8318531', expected '1662.8318531', error '0.0000000'

Test #28:

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

input:

10 243
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

2514.977871437821

result:

ok found '2514.9778714', expected '2514.9778714', error '0.0000000'

Test #29:

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

input:

7 478
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

4847.853981633974

result:

ok found '4847.8539816', expected '4847.8539816', error '0.0000000'

Test #30:

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

input:

400 400
OOOXXOXOXXXXXOXOXXOOXXXXOOXXXOXXOOXOXOOXOXOOOXXOXXOOOOXXOXOOXOXOXOXXXOOXOXOOXOOXXXOXXXXXXOOXXXXOXOXXXOOXOXOXXOOOOXXXXXOOXXXXXXXOOOXOXXXOXXOOOOXXOXXOXXOOOOXXOXOXOOXXOOXXXOOXOOOXXXXXXOOOXXOXOXOXOOOXOXOXXXXXXXXOXOOOXOXXOOXOXXXXOOXXXXXXOXOOXXXOXOOOOOXOXXOXXXXOOOXXOXOOOXOXOOOOXXXXOXXOXOOOOXOOXOXO...

output:

6823.981935418017

result:

ok found '6823.9819354', expected '6823.9819354', error '0.0000000'

Test #31:

score: 0
Accepted
time: 76ms
memory: 33292kb

input:

400 400
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

6285.331325545612

result:

ok found '6285.3313255', expected '6285.3313255', error '0.0000000'

Test #32:

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

input:

400 400
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

8000.000000000000

result:

ok found '8000.0000000', expected '8000.0000000', error '0.0000000'

Test #33:

score: 0
Accepted
time: 69ms
memory: 30636kb

input:

400 400
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXX...

output:

7854.070751110265

result:

ok found '7854.0707511', expected '7854.0707511', error '0.0000000'

Test #34:

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

input:

400 400
OOOOOOOXOOOOXOOOOXOXOOOOOOXOOOOOOOXOOOOOOOOOOXOOOOXOOOXOOXOOOOOOOOOOOXOOXOXOOOOOOOOOOOOOOXOOXXOXOOOOOOXOXOOOXOOOOOOOXXOOOXOOOXOXOOOOXOOOOOOOOOOOXXOXOOOXXOOOOOOOOOOOOXOOOOXOOOXOOXOOOXOOOOOXXOOOXOOOOOOOOOOOOOOXOOOOOOOXXOOOOXXOOOOOOOOXOOOOOXOOOXOOXOOOOOOOOXOOOOOOXOOOOOOOOXOXOOOOOXXOOOOOOOOOXXXO...

output:

6478.472978487908

result:

ok found '6478.4729785', expected '6478.4729785', error '0.0000000'

Test #35:

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

input:

700 700
XXXOXOXOXOOXOOXXXOOOOOXXXXOXOXOOXXOXXXOOOOOXXOXOXXXXOOOXXOXXXOXXXXXOXXXOOXXOOXOOXOXXOOXXXOOOXOOOOXXOXOOXOOXXOOXOOOXXXXOXOXOXOOOXOOXOOXXOOOXOOXOOOOXXXXXXOOXOOXXXOOOOXOOXOOXOXOOOOXOXOOXXXOXXOXOXOXXXXXOXXOOOOXXXOXOXXXOXXXXOOOXXXOXXOXXOXOOOOOOXOXOXOXXXXOXXOXXOXXOOOXXOOXOXXXOXOXOOOXOOXOOOOXOOOOOO...

output:

11922.654221687299

result:

ok found '11922.6542217', expected '11922.6542217', error '0.0000000'

Test #36:

score: 0
Accepted
time: 250ms
memory: 52340kb

input:

700 700
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

10997.720305930301

result:

ok found '10997.7203059', expected '10997.7203059', error '0.0000000'

Test #37:

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

input:

700 700
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

14000.000000000000

result:

ok found '14000.0000000', expected '14000.0000000', error '0.0000000'

Test #38:

score: 0
Accepted
time: 233ms
memory: 53152kb

input:

700 700
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

13725.309649148734

result:

ok found '13725.3096491', expected '13725.3096491', error '0.0000000'

Test #39:

score: 0
Accepted
time: 269ms
memory: 52228kb

input:

700 700
OXOXOXXOOXOOOOXOOOXOOOOOOOOOOOXOXOOOOOOOOOOXXOOOOXOXXOOOOOOOOOXOOOOOOOXOOOOOOOXOXXOOOOOOOXOOOOOOOOOOOXOOOOOOOOXOOOOOXOOOOOXOOOOXOXOOXOOOOOOXOOOXXOXOOOOOOOOOOOOXXOOOOOOOXOOOXOOOXOOOOXOOOOOOOOXOOOOOOXOOOOOXOXXXOOOOOOOOXXOOOOXOOOOOOXXXOOOOOXOOOOOOOXOOOOXOXXOOOOOXOOOOOOXXXXOOOXOOOOOOOOOOXXOXXXOO...

output:

11334.645189396308

result:

ok found '11334.6451894', expected '11334.6451894', error '0.0000000'

Test #40:

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

input:

573 492
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

9355.950925286613

result:

ok found '9355.9509253', expected '9355.9509253', error '0.0000000'

Test #41:

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

input:

139 271
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
XOOOOOOOOOOOOOOOOOOO...

output:

3503.406894244906

result:

ok found '3503.4068942', expected '3503.4068942', error '0.0000000'

Test #42:

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

input:

150 484
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOOOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

6335.707963267949

result:

ok found '6335.7079633', expected '6335.7079633', error '0.0000000'

Test #43:

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

input:

484 308
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

6598.052686528281

result:

ok found '6598.0526865', expected '6598.0526865', error '0.0000000'

Test #44:

score: 0
Accepted
time: 52ms
memory: 30676kb

input:

375 317
OXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

6173.185608623120

result:

ok found '6173.1856086', expected '6173.1856086', error '0.0000000'

Test #45:

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

input:

285 578
OOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

7406.769531365455

result:

ok found '7406.7695314', expected '7406.7695314', error '0.0000000'

Test #46:

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

input:

359 307
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

6655.707963267949

result:

ok found '6655.7079633', expected '6655.7079633', error '0.0000000'

Test #47:

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

input:

172 354
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

4521.769682087222

result:

ok found '4521.7696821', expected '4521.7696821', error '0.0000000'

Test #48:

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

input:

116 181
XOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXOOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

2658.827336926300

result:

ok found '2658.8273369', expected '2658.8273369', error '0.0000000'

Test #49:

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

input:

262 615
XXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

7645.486376202629

result:

ok found '7645.4863762', expected '7645.4863762', error '0.0000000'

Test #50:

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

input:

286 520
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOOXXXXXXXXXXXXXXXXXXXXXXXX...

output:

8055.707963267949

result:

ok found '8055.7079633', expected '8055.7079633', error '0.0000000'

Test #51:

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

input:

675 245
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

8148.451000647497

result:

ok found '8148.4510006', expected '8148.4510006', error '0.0000000'

Test #52:

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

input:

166 488
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

6136.548547187203

result:

ok found '6136.5485472', expected '6136.5485472', error '0.0000000'

Test #53:

score: 0
Accepted
time: 164ms
memory: 47052kb

input:

613 513
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

9058.185156457819

result:

ok found '9058.1851565', expected '9058.1851565', error '0.0000000'

Test #54:

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

input:

625 460
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

10845.707963267949

result:

ok found '10845.7079633', expected '10845.7079633', error '0.0000000'

Test #55:

score: 0
Accepted
time: 161ms
memory: 40108kb

input:

515 604
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

8979.601082993717

result:

ok found '8979.6010830', expected '8979.6010830', error '0.0000000'

Test #56:

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

input:

10 12
XXXXXXXXXXXO
XXXXXXXXXXXX
XXXXXXXXXXXX
XXXXXXXXXXXX
XXXXXXXXXXXX
XXXXXXXXXXXX
XXXXXXXXXXXX
XXXXXXXXXXXX
XXXXXXXXXXXX
XXXXXXXXXXXX

output:

217.853981633974

result:

ok found '217.8539816', expected '217.8539816', error '0.0000000'

Test #57:

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

input:

10 12
XXXXXXXXXXXX
XXXXXXXXXXXX
XXXXXXXXXXXX
XXXXXXXXXXXX
XXXXXXXXXXXX
XXXXXXXXXXXX
XXXXXXXXXXXX
XXXXXXXXXXXX
XXXXXXXXXXXX
XOXXXXXXXXXX

output:

217.853981633974

result:

ok found '217.8539816', expected '217.8539816', error '0.0000000'

Test #58:

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

input:

10 12
XXXXXXXXXXXX
XXXXXXXXXXXX
XXXXXXXXXXXX
XXXXXXXXXXXX
XXXXXXXXOXXX
XXXXXXXXXXXX
XXXXXXXXXXXX
XXXXXXXXXXXX
XXXXXXXXXXXX
XXXXXXXXXXXX

output:

217.853981633974

result:

ok found '217.8539816', expected '217.8539816', error '0.0000000'

Test #59:

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

input:

10 12
XXXXOXXXXOXO
XXXXOXOXOXXO
XXXOXXXXXOXX
OXOXXXXXXXXX
XXXXXXXXXOXX
XXXXXXOXOXXX
XXXOXOXXXXXX
XXOXXOXXXXXX
XOXXXXXXXXXX
OXXXXXXXXXXX

output:

211.415926535898

result:

ok found '211.4159265', expected '211.4159265', error '0.0000000'

Test #60:

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

input:

10 12
XXXOXXOXXXXX
XOOXXXXXOXXX
XXXOXXOXXOXX
XOXOXXXXXXOX
XXOXXOOXXXXX
OXXXXXOOXXXX
XOOXXOXXOXXX
XXXXOXXXOXXX
XOXXXXOXXOOX
XXXXOXXXXXXX

output:

194.247779607694

result:

ok found '194.2477796', expected '194.2477796', error '0.0000000'

Test #61:

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

input:

10 12
XXXXXXXXXXXO
XXXXXXXXXXOX
XXXXXXXXXOXX
XXXXXXXXOXXX
XXXXXXXOXXXX
XXXXXOOXXXXX
XXXOXXXXXXXX
XXOXXXXXXXXX
XOXXXXXXXXXX
OXXXXXXXXXXX

output:

215.707963267949

result:

ok found '215.7079633', expected '215.7079633', error '0.0000000'

Test #62:

score: 0
Accepted
time: 163ms
memory: 49084kb

input:

640 552
OOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

10413.495107050087

result:

ok found '10413.4951071', expected '10413.4951071', error '0.0000000'

Test #63:

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

input:

415 230
XOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXX
XXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXX...

output:

5840.530784048753

result:

ok found '5840.5307840', expected '5840.5307840', error '0.0000000'

Test #64:

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

input:

446 514
OXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

8421.835917051991

result:

ok found '8421.8359171', expected '8421.8359171', error '0.0000000'

Test #65:

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

input:

436 381
XXOOOOOXXXXXXXXXXOXXXXOXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXOXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXOXXXXXXXXXXXXXXXOXXXXXXXXXXOXXOOXXXOOXXOXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXOXXXXOXXXXOXXXXXXXXXXXXXXXXX...

output:

7139.911184307752

result:

ok found '7139.9111843', expected '7139.9111843', error '0.0000000'

Test #66:

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

input:

200 258
XOXXXXXXXXOXXXXXXOXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXOXXXXXXXXXXXXXXXXOXXOXXXXXOXOXOXXXXXOXXXXXXXOXXXXOXXXXXXXXXXXXXXOXXXXXXXXOOXXXXXXXXXXXXXXOXXXXXXXXXXOXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXOXXXXXXXXXXXXOOXXXXXXXXXXXOXXXXXXXXXXOXXXXXXXXXXXXXXX
XOOOXOXXXXXXXXXXXXXXXXXXXXXXXXXOX...

output:

4041.349390127595

result:

ok found '4041.3493901', expected '4041.3493901', error '0.0000000'

Test #67:

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

input:

3 3
XXO
XXX
XXX

output:

57.853981633974

result:

ok found '57.8539816', expected '57.8539816', error '0.0000000'

Test #68:

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

input:

3 3
XXX
XXX
OXX

output:

57.853981633974

result:

ok found '57.8539816', expected '57.8539816', error '0.0000000'

Test #69:

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

input:

3 3
XXX
OXX
XXX

output:

57.853981633974

result:

ok found '57.8539816', expected '57.8539816', error '0.0000000'

Test #70:

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

input:

3 3
XXX
XXO
XXX

output:

57.853981633974

result:

ok found '57.8539816', expected '57.8539816', error '0.0000000'

Test #71:

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

input:

3 3
XOX
XXX
XXX

output:

57.853981633974

result:

ok found '57.8539816', expected '57.8539816', error '0.0000000'

Test #72:

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

input:

3 3
XXX
XXX
XOX

output:

57.853981633974

result:

ok found '57.8539816', expected '57.8539816', error '0.0000000'

Test #73:

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

input:

3 3
XOO
XXO
XXX

output:

53.561944901923

result:

ok found '53.5619449', expected '53.5619449', error '0.0000000'

Test #74:

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

input:

3 3
XXX
OXX
OOX

output:

53.561944901923

result:

ok found '53.5619449', expected '53.5619449', error '0.0000000'