QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#501269#5153. Delft DistancexixuAC ✓298ms263732kbC++204.5kb2024-08-02 16:13:242024-08-02 16:13:25

Judging History

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

  • [2024-08-02 16:13:25]
  • 评测
  • 测评结果:AC
  • 用时:298ms
  • 内存:263732kb
  • [2024-08-02 16:13:24]
  • 提交

answer

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int , int> PII;


const int M = 2e7 + 10 , inf = 0x3f3f3f3f , N = 1500;
const double PI = 3.1415926535;


typedef pair<int, int> PII;
typedef pair<double , pair<int , int>> PL;

int n , m;      // 点的数量
PII e[M];
int ne[M];
double w[M];
int idx;       // 邻接表存储所有边
int h[N][N];
double dist[N][N];
bool st[N][N];
// double dist[N];        // 存储所有点到1号点的距离
// bool st[N];     // 存储每个点的最短距离是否已确定

void add(PII a , PII b , double c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a.first][a.second];
    h[a.first][a.second] = idx ++;
}

// 求1号点到n号点的最短距离,如果不存在,则返回-1
double dijkstra()
{
    // memset(dist, 0x3f, sizeof dist);
    for(int i = 1; i <= 2 * n + 2; i ++)
    {
        for(int j = 1; j <= 2 * m + 2; j ++)
        {
            dist[i][j] = inf;
        }
    }
    dist[1][1] = 0;

    priority_queue<PL, vector<PL>, greater<PL>> heap;
    heap.push({0, {1 , 1}});      // first存储距离,second存储节点编号

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();
        // cout << t.second.first << ' ' << t.second.second << '\n';

        PII ver = t.second;
        double distance = t.first;

        if (st[ver.first][ver.second]) continue;
        st[ver.first][ver.second] = true;

        for (int i = h[ver.first][ver.second]; i != -1; i = ne[i])
        {
            PII j = e[i];
            if (dist[j.first][j.second] > distance + w[i])
            {
                dist[j.first][j.second] = distance + w[i];
                heap.push({dist[j.first][j.second], j});
            }
        }
    }

    return dist[2 * n + 1][2 * m + 1];
}





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

    for(int i = 0; i <= 2 * n + 2; i ++)
    {
        for(int j = 0; j <= 2 * m + 2; j ++)
        {
            h[i][j] = -1;
        }
    }

    for(int i = 1; i < 2 * n; i += 2)
    {
        for(int j = 1; j < 2 * m; j += 2)
        {
            // cout << i << ' ' << j << '\n';
            char c;
            cin >> c;
            if(c == 'X')
            {
                add({i , j} , {i , j + 2} , 10);
                add({i , j + 2} , {i , j} , 10);

                add({i , j} , {i + 2 , j} , 10);
                add({i + 2 , j} , {i , j} , 10);

                add({i , j + 2} , {i + 2 , j + 2} , 10);
                add({i + 2 , j + 2} , {i , j + 2} , 10);

                add({i + 2 , j} , {i + 2 , j + 2} , 10);
                add({i + 2 , j + 2} , {i + 2 , j} , 10);
            }
            else
            {
                add({i ,j} , {i + 1 , j} , 5);
                add({i + 1 , j} , {i , j} , 5);

                add({i + 1 , j} , {i + 2 , j} , 5);
                add({i + 2 , j} , {i + 1 , j} , 5);

                add({i + 2 , j} , {i + 2 , j + 1} , 5);
                add({i + 2 , j + 1} , {i + 2 , j} , 5);

                add({i + 2 , j + 1} , {i + 2 , j + 2} , 5);
                add({i + 2 , j + 2} , {i + 2 , j + 1} , 5);

                add({i + 2 , j + 2} , {i + 1 , j + 2} , 5);
                add({i + 1 , j + 2} , {i + 2 , j + 2} , 5);

                add({i + 1 , j + 2} ,{i , j + 2} , 5);
                add({i ,j + 2} , {i + 1 , j + 2} , 5);

                add({i , j + 2} , {i , j + 1} , 5);
                add({i , j + 1} , {i , j + 2} , 5);

                add({i , j + 1} , {i , j} , 5);
                add({i , j} , {i , j + 1} , 5);

                add({i + 1 , j} , {i , j + 1} , 5 * PI / 2);
                add({i , j + 1} , {i + 1 , j} , 5 * PI / 2);

                // cout << 5 * PI / 2 << '\n';
                add({i , j + 1} , {i + 1 , j + 2} , 5 * PI / 2);
                add({i + 1 , j + 2} , {i , j + 1} , 5 * PI / 2);

                add({i + 1 , j + 2} , {i + 2 , j + 1} , 5 * PI / 2);
                add({i + 2 , j + 1} , {i + 1 , j + 2} , 5 * PI / 2);

                add({i + 2 , j + 1} , {i + 1 , j} , 5 * PI / 2);
                add({i + 1 , j} , {i + 2 , j + 1} , 5 * PI / 2);
            }

        }
    }

    cout << fixed << setprecision(12) << dijkstra() << '\n';


}



signed main()
{
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while(t --)
    {
        solve();
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 5
XOOXO
OXOXO
XXXXO

output:

71.415926535000

result:

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

Test #2:

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

input:

1 4
XOOX

output:

45.707963267500

result:

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

Test #3:

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

input:

1 1
X

output:

20.000000000000

result:

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

Test #4:

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

input:

1 1
O

output:

17.853981633750

result:

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

Test #5:

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

input:

1 3
XOO

output:

35.707963267500

result:

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

Test #6:

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

input:

1 5
OXOOO

output:

55.707963267500

result:

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

Test #7:

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

input:

6 10
XXXXXOOOOX
XXOOOOOOOO
XXXOXOOXOX
OXOXOXXOOX
OOXXOXXXXO
OXOXXOOXOO

output:

142.831853070000

result:

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

Test #8:

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

input:

1 2
XX

output:

30.000000000000

result:

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

Test #9:

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

input:

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

output:

105.707963267500

result:

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

Test #10:

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

input:

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

output:

214.247779605000

result:

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

Test #11:

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

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

result:

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

Test #12:

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

input:

41 50
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXO
XXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXOXXXXXXXXXXXXXXX
XXXXXXXXXXXXXOXXXXXXXXXXXXXXOXXXXXXXXXX...

output:

873.517687773750

result:

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

Test #13:

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

input:

329 527
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

8560.000000000000

result:

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

Test #14:

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

input:

49 297
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

3451.415926535000

result:

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

Test #15:

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

input:

357 83
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

4342.057504111252

result:

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

Test #16:

score: 0
Accepted
time: 50ms
memory: 74156kb

input:

417 615
XXXXXXXXOXXXXXXXXXXXOXXXXXXXXXXXOXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXOXXXXXXXXXXXXXXOXXXXXOXXXOOXXXXXXXXXXXXXXXXXXXXXOXOXXOXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXOXXXXXXOXXXXXXXXOXXXXXXXOXXXXXXXXXXXXXXXXOXXXXXXOXXXXXXXOXXXXXXXXXXOXXXXXXXXOXXXOXXXOXXXXXOXXXOXXXXXXXXXOXXXXXXXXXXXXXXXXXXXX...

output:

9736.283004380010

result:

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

Test #17:

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

input:

359 225
OOOOXXOOXOXXXOOOOOXOXOOOXOOXXXXXOOOXOXXXOOOOXXOXXOOXOXOXXOXOXXXOXXXXXOOOXXXXXXXOOOOXXXXXOOXOXXOXOXOXXOXOXXOXOXOOOXOXXXOOXOXOXXXXOXOOXXOXXOXOXOXXOXXXOOOXXOOOXXOXXXXXOXOXOOXXOOXOXXOXXOOOOOXOXOOXXXOOXOOXOOOOXOXOOXXOOOXOOOXXXXOXX
OXOOOXXXOOXOOXOOXXOOXXOOXXOXXOOOOOXOXXOOXXXOXXXOXOOOXOOXXOOXOXXOXO...

output:

5026.659039191263

result:

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

Test #18:

score: 0
Accepted
time: 60ms
memory: 72088kb

input:

261 431
OOOOOOOXOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOOXOOOOOOXOOOXXOOOOOOOOOOOOOOXOOXOOOOOOXOOOOOOOOOXOOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOXOXOOOOOOOOOOOOOXOOOXOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOOOOXOOOOOOOOOXXOOXOOOOOOOOOOOXOOXOOOOXOXXOOOOOOOOOOXOXOOOOOOOOOOOOOXOOOOOOOOOOOOOXOOOOOOOOXOOOOOOOOOOO...

output:

5799.778412817474

result:

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

Test #19:

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

input:

37 427
OOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

4481.194640897487

result:

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

Test #20:

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

input:

105 430
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

4899.336143087473

result:

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

Test #21:

score: 0
Accepted
time: 117ms
memory: 132224kb

input:

465 484
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

7494.202919387440

result:

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

Test #22:

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

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

result:

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

Test #23:

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

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

result:

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

Test #24:

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

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

result:

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

Test #25:

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

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

result:

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

Test #26:

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

input:

4 204
OXOOXXXOOOXOOXXOXOXXXXOXXXXOXXXOXXOXXOXOOXOOOOXXXOXOXXXOXOOOOOXOXXXOOXOXXXXOXOOXXXOXOXOXXXOXOXXOOOXOOOXOXXXOXOOXXOOXOOOOOXOOOOOOXOXOXXOOOXXXXOOOXOOOXOOOOXXOXXOOXOXXOXOOXOOXXXOOXXOOXXXXOOOXOXXXXOOXXOOOOXXO
OXXXXXOOXOOXOXOOXOXOOOOXXOXOOOOOXOOOXOOOXOXXXOXXOXXXOOXOOXXXXXOXOXXXXXXOOXXOXXXXXOXOXOOXO...

output:

2062.831853070000

result:

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

Test #27:

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

input:

4 164
XXXXXXXXXXXXOXXXXOXXXXXXXXXXXXXXXXXXXXXXOXOXOOXOXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXOXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXOXXXXXXXXXXXXXXXXOXXXO
XXXOXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXOXXXXXXXXXXXXOOXXXXXXOXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXOXXX...

output:

1662.831853070000

result:

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

Test #28:

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

input:

10 243
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

2514.977871436250

result:

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

Test #29:

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

input:

7 478
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

4847.853981633750

result:

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

Test #30:

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

input:

400 400
OOOXXOXOXXXXXOXOXXOOXXXXOOXXXOXXOOXOXOOXOXOOOXXOXXOOOOXXOXOOXOXOXOXXXOOXOXOOXOOXXXOXXXXXXOOXXXXOXOXXXOOXOXOXXOOOOXXXXXOOXXXXXXXOOOXOXXXOXXOOOOXXOXXOXXOOOOXXOXOXOOXXOOXXXOOXOOOXXXXXXOOOXXOXOXOXOOOXOXOXXXXXXXXOXOOOXOXXOOXOXXXXOOXXXXXXOXOOXXXOXOOOOOXOXXOXXXXOOOXXOXOOOXOXOOOOXXXXOXXOXOOOOXOOXOXO...

output:

6823.981935294978

result:

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

Test #31:

score: 0
Accepted
time: 109ms
memory: 97840kb

input:

400 400
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

6285.331325366232

result:

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

Test #32:

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

input:

400 400
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

8000.000000000000

result:

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

Test #33:

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

input:

400 400
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXX...

output:

7854.070751094995

result:

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

Test #34:

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

input:

400 400
OOOOOOOXOOOOXOOOOXOXOOOOOOXOOOOOOOXOOOOOOOOOOXOOOOXOOOXOOXOOOOOOOOOOOXOOXOXOOOOOOOOOOOOOOXOOXXOXOOOOOOXOXOOOXOOOOOOOXXOOOXOOOXOXOOOOXOOOOOOOOOOOXXOXOOOXXOOOOOOOOOOOOXOOOOXOOOXOOXOOOXOOOOOXXOOOXOOOOOOOOOOOOOOXOOOOOOOXXOOOOXXOOOOOOOOXOOOOOXOOOXOOXOOOOOOOOXOOOOOOXOOOOOOOOXOXOOOOOXXOOOOOOOOOXXXO...

output:

6478.472978328728

result:

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

Test #35:

score: 0
Accepted
time: 236ms
memory: 187492kb

input:

700 700
XXXOXOXOXOOXOOXXXOOOOOXXXXOXOXOOXXOXXXOOOOOXXOXOXXXXOOOXXOXXXOXXXXXOXXXOOXXOOXOOXOXXOOXXXOOOXOOOOXXOXOOXOOXXOOXOOOXXXXOXOXOXOOOXOOXOOXXOOOXOOXOOOOXXXXXXOOXOOXXXOOOOXOOXOOXOXOOOOXOXOOXXXOXXOXOXOXXXXXOXXOOOOXXXOXOXXXOXXXXOOOXXXOXXOXXOXOOOOOOXOXOXOXXXXOXXOXXOXXOOOXXOOXOXXXOXOXOOOXOOXOOOOXOOOOOO...

output:

11922.654221470149

result:

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

Test #36:

score: 0
Accepted
time: 298ms
memory: 263732kb

input:

700 700
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

10997.720305616409

result:

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

Test #37:

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

input:

700 700
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

14000.000000000000

result:

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

Test #38:

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

input:

700 700
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

13725.309649120030

result:

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

Test #39:

score: 0
Accepted
time: 285ms
memory: 232876kb

input:

700 700
OXOXOXXOOXOOOOXOOOXOOOOOOOOOOOXOXOOOOOOOOOOXXOOOOXOXXOOOOOOOOOXOOOOOOOXOOOOOOOXOXXOOOOOOOXOOOOOOOOOOOXOOOOOOOOXOOOOOXOOOOOXOOOOXOXOOXOOOOOOXOOOXXOXOOOOOOOOOOOOXXOOOOOOOXOOOXOOOXOOOOXOOOOOOOOXOOOOOOXOOOOOXOXXXOOOOOOOOXXOOOOXOOOOOOXXXOOOOOXOOOOOOOXOOOOXOXXOOOOOXOOOOOOXXXXOOOXOOOOOOOOOOXXOXXXOO...

output:

11334.645189117660

result:

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

Test #40:

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

input:

573 492
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

9355.950925151225

result:

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

Test #41:

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

input:

139 271
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
XOOOOOOOOOOOOOOOOOOO...

output:

3503.406894182501

result:

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

Test #42:

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

input:

150 484
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOOOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

6335.707963267500

result:

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

Test #43:

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

input:

484 308
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

6598.052686389927

result:

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

Test #44:

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

input:

375 317
OXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

6173.185608545005

result:

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

Test #45:

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

input:

285 578
OOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

7406.769531237394

result:

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

Test #46:

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

input:

359 307
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

6655.707963267500

result:

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

Test #47:

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

input:

172 354
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

4521.769682009990

result:

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

Test #48:

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

input:

116 181
XOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXOOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

2658.827336893748

result:

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

Test #49:

score: 0
Accepted
time: 80ms
memory: 99980kb

input:

262 615
XXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

7645.486376084888

result:

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

Test #50:

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

input:

286 520
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOOXXXXXXXXXXXXXXXXXXXXXXXX...

output:

8055.707963267500

result:

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

Test #51:

score: 0
Accepted
time: 75ms
memory: 105816kb

input:

675 245
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

8148.451000537380

result:

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

Test #52:

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

input:

166 488
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

6136.548547145008

result:

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

Test #53:

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

input:

613 513
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

9058.185156227419

result:

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

Test #54:

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

input:

625 460
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

10845.707963267500

result:

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

Test #55:

score: 0
Accepted
time: 183ms
memory: 171764kb

input:

515 604
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

8979.601082762420

result:

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

Test #56:

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

input:

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

output:

217.853981633750

result:

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

Test #57:

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

input:

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

output:

217.853981633750

result:

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

Test #58:

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

input:

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

output:

217.853981633750

result:

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

Test #59:

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

input:

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

output:

211.415926535000

result:

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

Test #60:

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

input:

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

output:

194.247779605000

result:

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

Test #61:

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

input:

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

output:

215.707963267500

result:

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

Test #62:

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

input:

640 552
OOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

10413.495106892544

result:

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

Test #63:

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

input:

415 230
XOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXX
XXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXX...

output:

5840.530783985025

result:

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

Test #64:

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

input:

446 514
OXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

8421.835916928711

result:

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

Test #65:

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

input:

436 381
XXOOOOOXXXXXXXXXXOXXXXOXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXOXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXOXXXXXXXXXXXXXXXOXXXXXXXXXXOXXOOXXXOOXXOXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXOXXXXOXXXXOXXXXXXXXXXXXXXXXX...

output:

7139.911184199978

result:

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

Test #66:

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

input:

200 258
XOXXXXXXXXOXXXXXXOXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXOXXXXXXXXXXXXXXXXOXXOXXXXXOXOXOXXXXXOXXXXXXXOXXXXOXXXXXXXXXXXXXXOXXXXXXXXOOXXXXXXXXXXXXXXOXXXXXXXXXXOXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXOXXXXXXXXXXXXOOXXXXXXXXXXXOXXXXXXXXXXOXXXXXXXXXXXXXXX
XOOOXOXXXXXXXXXXXXXXXXXXXXXXXXXOX...

output:

4041.349390071268

result:

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

Test #67:

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

input:

3 3
XXO
XXX
XXX

output:

57.853981633750

result:

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

Test #68:

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

input:

3 3
XXX
XXX
OXX

output:

57.853981633750

result:

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

Test #69:

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

input:

3 3
XXX
OXX
XXX

output:

57.853981633750

result:

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

Test #70:

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

input:

3 3
XXX
XXO
XXX

output:

57.853981633750

result:

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

Test #71:

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

input:

3 3
XOX
XXX
XXX

output:

57.853981633750

result:

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

Test #72:

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

input:

3 3
XXX
XXX
XOX

output:

57.853981633750

result:

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

Test #73:

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

input:

3 3
XOO
XXO
XXX

output:

53.561944901250

result:

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

Test #74:

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

input:

3 3
XXX
OXX
OOX

output:

53.561944901250

result:

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