QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#96493#5153. Delft DistanceAhmed_AbdelmegeedTL 3070ms89432kbC++207.0kb2023-04-13 22:24:432023-04-13 22:24:44

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 22:24:44]
  • 评测
  • 测评结果:TL
  • 用时:3070ms
  • 内存:89432kb
  • [2023-04-13 22:24:43]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ld long double
#define el "\n"
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ordered_multiset tree<ll, null_type,less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
const ll N = 700 + 10, INF = 1e18;
const ld pi = acos(-1);
const int mod = 1e9 + 7, LOG = 20;
const ld eps = 1e-4;
int dx[] = {0, -1, 0, 1, -1, 1, -1, 1};
int dy[] = {-1, 0, 1, 0, 1, -1, -1, 1};
ll n, m, k, x, y;
ld sidecircle = 0.5 * pi * 5;
ld dis[N][N][10], vis[N][N][10];
char grid[N][N];

void zbtsquare(int x, int y) {
    ld cur;
    for (int i = 0; i < 8; i++) {
        cur = 0;
        for (int j = i; j < i + 8; j++) {
            dis[x][y][j % 8] = min(cur + dis[x][y][i], dis[x][y][j % 8]);
            cur += 5;
        }
        cur = 0;
        for (int j = i; j > i - 8; j--) {
            dis[x][y][(j + 8) % 8] = min(cur + dis[x][y][i], dis[x][y][(j + 8) % 8]);
            cur += 5;
        }
    }
}

void zbtcircle(int x, int y) {
    ld cur;
    for (int i = 1; i < 8; i += 2) {
        cur = 0;
        for (int j = i; j < i + 8; j += 2) {
            //cout << x << " " << y << " " << j << " " << cur + dis[x][y][i] << el;
            dis[x][y][j % 8] = min(cur + dis[x][y][i], dis[x][y][j % 8]);
            cur += sidecircle;
        }
        cur = 0;
        for (int j = i; j > i - 8; j -= 2) {
            //cout << x << " " << y << " " << j << " " << cur + dis[x][y][i] << el;
            dis[x][y][(j + 8) % 8] = min(cur + dis[x][y][i], dis[x][y][(j + 8) % 8]);
            cur += sidecircle;
        }
    }
}

bool valid(int x, int y) {
    return (x >= 1 && x <= n && y >= 1 && y <= m);
}

void trantition(int x, int y, priority_queue<pair<ld, pair<pair<int, int>, int>>> &pq) {
    if (valid(x + 1, y - 1)) {
        if (dis[x + 1][y - 1][2] > dis[x][y][6]) {
            dis[x + 1][y - 1][2] = dis[x][y][6];
            pq.push({-dis[x + 1][y - 1][2], {{x + 1, y - 1}, 2}});
        }
    }
    if (valid(x + 1, y - 1)) {
        if (dis[x][y + 1][0] > dis[x][y][2]) {
            dis[x][y + 1][0] = dis[x][y][2];
            pq.push({-dis[x][y + 1][0], {{x, y + 1}, 0}});
        }
        if (dis[x][y + 1][7] > dis[x][y][3]) {
            dis[x][y + 1][7] = dis[x][y][3];
            pq.push({-dis[x][y + 1][7], {{x, y + 1}, 7}});
        }
        if (dis[x][y + 1][6] > dis[x][y][4]) {
            dis[x][y + 1][6] = dis[x][y][4];
            pq.push({-dis[x][y + 1][6], {{x, y + 1}, 6}});
        }
    }
    if (valid(x + 1, y + 1)) {
        if (dis[x + 1][y + 1][0] > dis[x][y][4]) {
            dis[x + 1][y + 1][0] = dis[x][y][4];
            pq.push({-dis[x + 1][y + 1][0], {{x + 1, y + 1}, 0}});
        }
    }
    if (valid(x + 1, y)) {
        if (dis[x + 1][y][2] > dis[x][y][4]) {
            dis[x + 1][y][2] = dis[x][y][4];
            pq.push({-dis[x + 1][y][2], {{x + 1, y}, 2}});
        }
        if (dis[x + 1][y][1] > dis[x][y][5]) {
            dis[x + 1][y][1] = dis[x][y][5];
            pq.push({-dis[x + 1][y][1], {{x + 1, y}, 1}});
        }
        if (dis[x + 1][y][0] > dis[x][y][6]) {
            dis[x + 1][y][0] = dis[x][y][6];
            pq.push({-dis[x + 1][y][0], {{x + 1, y}, 0}});
        }
    }
    if (valid(x - 1, y + 1)) {
        if (dis[x - 1][y + 1][6] > dis[x][y][2]) {
            dis[x - 1][y + 1][6] = dis[x][y][2];
            pq.push({-dis[x - 1][y + 1][6], {{x + 1, y}, 6}});
        }
    }
    if (valid(x, y - 1)) {
        if (dis[x][y - 1][2] > dis[x][y][0]) {
            dis[x][y - 1][2] = dis[x][y][0];
            pq.push({-dis[x][y - 1][2], {{x, y - 1}, 2}});
        }
        if (dis[x][y - 1][3] > dis[x][y][7]) {
            dis[x][y - 1][3] = dis[x][y][7];
            pq.push({-dis[x][y - 1][3], {{x, y - 1}, 3}});
        }
        if (dis[x][y - 1][4] > dis[x][y][6]) {
            dis[x][y - 1][4] = dis[x][y][6];
            pq.push({-dis[x][y - 1][4], {{x, y - 1}, 4}});
        }
    }
    if (valid(x - 1, y - 1)) {
        if (dis[x - 1][y - 1][4] > dis[x][y][0]) {
            dis[x - 1][y - 1][4] = dis[x][y][0];
            pq.push({-dis[x - 1][y - 1][4], {{x - 1, y - 1}, 4}});
        }
    }
    if (valid(x - 1, y)) {
        if (dis[x - 1][y][6] > dis[x][y][0]) {
            dis[x - 1][y][6] = dis[x][y][0];
            pq.push({-dis[x - 1][y][6], {{x - 1, y}, 6}});
        }
        if (dis[x - 1][y][5] > dis[x][y][1]) {
            dis[x - 1][y][5] = dis[x][y][1];
            pq.push({-dis[x - 1][y][5], {{x - 1, y}, 5}});
        }
        if (dis[x - 1][y][4] > dis[x][y][2]) {
            dis[x - 1][y][4] = dis[x][y][2];
            pq.push({-dis[x - 1][y][4], {{x - 1, y}, 4}});
        }
    }
    if (valid(x, y + 1)) {
        if (dis[x][y + 1][0] > dis[x][y][2]) {
            dis[x][y + 1][0] = dis[x][y][2];
            pq.push({-dis[x][y + 1][0], {{x, y + 1}, 0}});
        }
        if (dis[x][y + 1][7] > dis[x][y][3]) {
            dis[x][y + 1][7] = dis[x][y][3];
            pq.push({-dis[x][y + 1][7], {{x, y + 1}, 7}});
        }
        if (dis[x][y + 1][6] > dis[x][y][4]) {
            dis[x][y + 1][6] = dis[x][y][4];
            pq.push({-dis[x][y + 1][6], {{x, y + 1}, 6}});
        }
    }
    //cout << pq.size() << el;
}

void solve() {
    priority_queue<pair<ld, pair<pair<int, int>, int>>> pq;
    dis[1][1][0] = 0;
    pq.push({0, {{1, 1}, 0}});
    ld cost;
    int state;
    while (pq.size()) {
        x = pq.top().second.first.first;
        y = pq.top().second.first.second;
        cost = -pq.top().first;
        state = pq.top().second.second;
        pq.pop();
        if (dis[x][y][state] < cost) {
            continue;
        }
        zbtsquare(x, y);
        if (grid[x][y] == 'O') {
            zbtcircle(x, y);
            zbtsquare(x, y);
        }
        for (int i = 0; i < 8; i++) {
            //cout << dis[x][y][i] << el;
            if (vis[x][y][i] > dis[x][y][i]) {
                pq.push({-dis[x][y][i], {{x, y}, i}});
                //cout << x << " " << y << " " << i << el;
                vis[x][y][i] = dis[x][y][i];
            }
        }
        trantition(x, y, pq);
    }
}

void dowork() {
    cin >> n >> m;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= 8; k++) {
                dis[i][j][k] = vis[i][j][k] = 2e18;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> grid[i][j];
        }
    }
    solve();
    cout << fixed << setprecision(10) << dis[n][m][4] << el;
}

signed main() {
    fast
    int t = 1;
    //cin >> t;
    for (int i = 1; i <= t; i++) {
        dowork();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 5
XOOXO
OXOXO
XXXXO

output:

71.4159265359

result:

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

Test #2:

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

input:

1 4
XOOX

output:

45.7079632679

result:

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

Test #3:

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

input:

1 1
X

output:

20.0000000000

result:

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

Test #4:

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

input:

1 1
O

output:

17.8539816340

result:

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

Test #5:

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

input:

1 3
XOO

output:

35.7079632679

result:

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

Test #6:

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

input:

1 5
OXOOO

output:

55.7079632679

result:

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

Test #7:

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

input:

6 10
XXXXXOOOOX
XXOOOOOOOO
XXXOXOOXOX
OXOXOXXOOX
OOXXOXXXXO
OXOXXOOXOO

output:

142.8318530718

result:

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

Test #8:

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

input:

1 2
XX

output:

30.0000000000

result:

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

Test #9:

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

input:

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

output:

105.7079632679

result:

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

Test #10:

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

input:

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

output:

214.2477796077

result:

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

Test #11:

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

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.5176877776

result:

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

Test #12:

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

input:

41 50
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXO
XXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXOXXXXXXXXXXXXXXX
XXXXXXXXXXXXXOXXXXXXXXXXXXXXOXXXXXXXXXX...

output:

873.5176877776

result:

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

Test #13:

score: 0
Accepted
time: 1374ms
memory: 62980kb

input:

329 527
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

8560.0000000000

result:

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

Test #14:

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

input:

49 297
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

3451.4159265359

result:

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

Test #15:

score: 0
Accepted
time: 229ms
memory: 23336kb

input:

357 83
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

4342.0575041173

result:

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

Test #16:

score: 0
Accepted
time: 2169ms
memory: 89432kb

input:

417 615
XXXXXXXXOXXXXXXXXXXXOXXXXXXXXXXXOXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXOXXXXXXXXXXXXXXOXXXXXOXXXOOXXXXXXXXXXXXXXXXXXXXXOXOXXOXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXOXXXXXXOXXXXXXXXOXXXXXXXOXXXXXXXXXXXXXXXXOXXXXXXOXXXXXXXOXXXXXXXXXXOXXXXXXXXOXXXOXXXOXXXXXOXXXOXXXXXXXXXOXXXXXXXXXXXXXXXXXXXX...

output:

9736.2830044411

result:

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

Test #17:

score: 0
Accepted
time: 856ms
memory: 38252kb

input:

359 225
OOOOXXOOXOXXXOOOOOXOXOOOXOOXXXXXOOOXOXXXOOOOXXOXXOOXOXOXXOXOXXXOXXXXXOOOXXXXXXXOOOOXXXXXOOXOXXOXOXOXXOXOXXOXOXOOOXOXXXOOXOXOXXXXOXOOXXOXXOXOXOXXOXXXOOOXXOOOXXOXXXXXOXOXOOXXOOXOXXOXXOOOOOXOXOOXXXOOXOOXOOOOXOXOOXXOOOXOOOXXXXOXX
OXOOOXXXOOXOOXOOXXOOXXOOXXOXXOOOOOXOXXOOXXXOXXXOXOOOXOOXXOOXOXXOXO...

output:

5026.6590392763

result:

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

Test #18:

score: 0
Accepted
time: 1384ms
memory: 44724kb

input:

261 431
OOOOOOOXOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOOXOOOOOOXOOOXXOOOOOOOOOOOOOOXOOXOOOOOOXOOOOOOOOOXOOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOXOXOOOOOOOOOOOOOXOOOXOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOOOOXOOOOOOOOOXXOOXOOOOOOOOOOOXOOXOOOOXOXXOOOOOOOOOOXOXOOOOOOOOOOOOOXOOOOOOOOOOOOOXOOOOOOOOXOOOOOOOOOOO...

output:

5799.7784129347

result:

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

Test #19:

score: 0
Accepted
time: 196ms
memory: 11020kb

input:

37 427
OOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

4481.1946409141

result:

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

Test #20:

score: 0
Accepted
time: 560ms
memory: 21348kb

input:

105 430
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

4899.3361431346

result:

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

Test #21:

score: 0
Accepted
time: 3070ms
memory: 81112kb

input:

465 484
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

7494.2029195963

result:

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

Test #22:

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

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.6637061436

result:

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

Test #23:

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

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.1017612417

result:

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

Test #24:

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

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.8539816340

result:

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

Test #25:

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

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.7079632679

result:

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

Test #26:

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

input:

4 204
OXOOXXXOOOXOOXXOXOXXXXOXXXXOXXXOXXOXXOXOOXOOOOXXXOXOXXXOXOOOOOXOXXXOOXOXXXXOXOOXXXOXOXOXXXOXOXXOOOXOOOXOXXXOXOOXXOOXOOOOOXOOOOOOXOXOXXOOOXXXXOOOXOOOXOOOOXXOXXOOXOXXOXOOXOOXXXOOXXOOXXXXOOOXOXXXXOOXXOOOOXXO
OXXXXXOOXOOXOXOOXOXOOOOXXOXOOOOOXOOOXOOOXOXXXOXXOXXXOOXOOXXXXXOXOXXXXXXOOXXOXXXXXOXOXOOXO...

output:

2062.8318530718

result:

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

Test #27:

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

input:

4 164
XXXXXXXXXXXXOXXXXOXXXXXXXXXXXXXXXXXXXXXXOXOXOOXOXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXOXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXOXXXXXXXXXXXXXXXXOXXXO
XXXOXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXOXXXXXXXXXXXXOOXXXXXXOXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXOXXX...

output:

1662.8318530718

result:

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

Test #28:

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

input:

10 243
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

2514.9778714378

result:

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

Test #29:

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

input:

7 478
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

4847.8539816340

result:

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

Test #30:

score: 0
Accepted
time: 1673ms
memory: 59820kb

input:

400 400
OOOXXOXOXXXXXOXOXXOOXXXXOOXXXOXXOOXOXOOXOXOOOXXOXXOOOOXXOXOOXOXOXOXXXOOXOXOOXOOXXXOXXXXXXOOXXXXOXOXXXOOXOXOXXOOOOXXXXXOOXXXXXXXOOOXOXXXOXXOOOOXXOXXOXXOOOOXXOXOXOOXXOOXXXOOXOOOXXXXXXOOOXXOXOXOXOOOXOXOXXXXXXXXOXOOOXOXXOOXOXXXXOOXXXXXXOXOOXXXOXOOOOOXOXXOXXXXOOOXXOXOOOXOXOOOOXXXXOXXOXOOOOXOOXOXO...

output:

6823.9819354180

result:

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

Test #31:

score: 0
Accepted
time: 2037ms
memory: 59276kb

input:

400 400
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

6285.3313255456

result:

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

Test #32:

score: 0
Accepted
time: 1256ms
memory: 60092kb

input:

400 400
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

8000.0000000000

result:

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

Test #33:

score: 0
Accepted
time: 1301ms
memory: 60152kb

input:

400 400
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXX...

output:

7854.0707511103

result:

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

Test #34:

score: 0
Accepted
time: 1900ms
memory: 60152kb

input:

400 400
OOOOOOOXOOOOXOOOOXOXOOOOOOXOOOOOOOXOOOOOOOOOOXOOOOXOOOXOOXOOOOOOOOOOOXOOXOXOOOOOOOOOOOOOOXOOXXOXOOOOOOXOXOOOXOOOOOOOXXOOOXOOOXOXOOOOXOOOOOOOOOOOXXOXOOOXXOOOOOOOOOOOOXOOOOXOOOXOOXOOOXOOOOOXXOOOXOOOOOOOOOOOOOOXOOOOOOOXXOOOOXXOOOOOOOOXOOOOOXOOOXOOXOOOOOOOOXOOOOOOXOOOOOOOOXOXOOOOOXXOOOOOOOOOXXXO...

output:

6478.4729784879

result:

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

Test #35:

score: -100
Time Limit Exceeded

input:

700 700
XXXOXOXOXOOXOOXXXOOOOOXXXXOXOXOOXXOXXXOOOOOXXOXOXXXXOOOXXOXXXOXXXXXOXXXOOXXOOXOOXOXXOOXXXOOOXOOOOXXOXOOXOOXXOOXOOOXXXXOXOXOXOOOXOOXOOXXOOOXOOXOOOOXXXXXXOOXOOXXXOOOOXOOXOOXOXOOOOXOXOOXXXOXXOXOXOXXXXXOXXOOOOXXXOXOXXXOXXXXOOOXXXOXXOXXOXOOOOOOXOXOXOXXXXOXXOXXOXXOOOXXOOXOXXXOXOXOOOXOOXOOOOXOOOOOO...

output:


result: