QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#618311#5153. Delft DistanceRafat_KabirAC ✓3587ms509600kbC++205.9kb2024-10-06 20:51:002024-10-06 20:51:00

Judging History

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

  • [2024-10-06 20:51:00]
  • 评测
  • 测评结果:AC
  • 用时:3587ms
  • 内存:509600kb
  • [2024-10-06 20:51:00]
  • 提交

answer

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <time.h>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <cstring>

using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <iostream>

using namespace __gnu_pbds;
using namespace std;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// to erase in multiset-> less_equal<T> and 
// s.erase(s.find_by_order(s.order_of_key(x)))
// lower_bound(x)=>(cannot use the stl lower_bound function)
// ll idx = s.order_of_key(x)
// if(idx == s.size()) -> no lower_bound
// else lb = *s.find_by_order(idx) // as 0-indexing
// idx-1 will give highest value which is strictly less than x
// for upper_bound->do the same with (x+1)

typedef long long ll;
typedef long double ld;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
typedef tuple<ll, ll, ll> t64;
typedef vector<t64> vt64;
typedef vector<vt64> vvt64;
typedef pair<double,double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int> > vv32;
typedef vector<vector<ll> > vv64;
typedef vector<vector<p64> > vvp64;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
typedef vector<vector<p32> > vvp32;
typedef vector<bool> vb;
ll mod =  1e9+7, MOD = 998244353;
double eps = 1e-12;
// #define forn(i,e) for(ll i = 0; i < e; i++)
#define FOR(s, e, i) for(int i = s; i <= e; i++)
// #define rforn(i,s) for(ll i = s; i >= 0; i--)
#define ROF(s ,e, i) for(int i = s; i >= e; i--)
#define coutAll(A) for(auto asdafas : A) cout <<  asdafas << " "; cout << "\n";
#define foutAll(A) for(auto asdafas : A) fout <<  asdafas << " "; cout << "\n";
#define cinAll(A) for(auto &asdafas : A) cin >>  asdafas;
#define finAll(A) for(auto &asdafas : A) fin >>  asdafas;
#define minpq priority_queue<ll, v64, greater<ll>>
#define maxpq priority_queue<ll> 
#define ln "\n"
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define fi first
#define se second
ll inf = LLONG_MAX;
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef pair<ll, ll> pll;
typedef pair<ll, ll> pii;
//#define MAXN 1000000

void solve(int it)
{
    int h, w;
    cin >> h >> w;
    int H = 2*h+1;
    int W = 2*w+1;
    map<p32, ll>cmp;
    map<ll, p32>revcmp;
    int sz = 0;
    FOR(0, H - 1, i){
        FOR(0, W - 1, j){
            cmp[{i, j}] = sz;
            revcmp[sz] = {i, j};
            ++sz;
        }
    }
    vector<string>A(h); cinAll(A);
    int di[] = {1, -1, 0, 0};
    int dj[] = {0, 0, 1, -1};
    auto valid = [&](int i, int j)->bool{
        return 0 <= i && i < H && 0 <= j && j < W;
    };
    vector<vector<pair<int, double>>>adj(sz);
    FOR(0, H - 1, i){
        FOR(0, W - 1, j){
            if(i % 2 && j % 2) continue;
            if(i % 2 == 0 && j % 2 == 0)
                FOR(0, 3, d){
                    int ni = i + di[d];
                    int nj = j + dj[d];
                    if(valid(ni, nj)){
                        adj[cmp[{i, j}]].pb({cmp[{ni, nj}], 5});
                    }
                }
            else if(i % 2 == 1 && j % 2 == 0)
                FOR(0, 3, d){
                    if(di[d] == 0) continue;
                    int ni = i + di[d];
                    int nj = j + dj[d];
                    if(valid(ni, nj)){
                        adj[cmp[{i, j}]].pb({cmp[{ni, nj}], 5});
                    }
                }
            else
                FOR(0, 3, d){
                    if(dj[d] == 0) continue;
                    int ni = i + di[d];
                    int nj = j + dj[d];
                    if(valid(ni, nj)){
                        adj[cmp[{i, j}]].pb({cmp[{ni, nj}], 5});
                    }
                }
        }
    }
    auto add_edge = [&](int u, int v, double wt)->void{
        adj[u].pb({v, wt});
        adj[v].pb({u, wt});
    };
    double arc = acos(-1)*5.0/2;
    FOR(0, h - 1, i){
        FOR(0, w - 1, j){
            if(A[i][j] == 'O'){
                int I = 2*i, J = 2*j+1;
                int _I = 2*i+2, _J = 2*j+1;
                int I_ = 2*i+1, J_ = 2*j;
                int I__ = 2*i+1, J__ = 2*j+2;
                add_edge(cmp[{I, J}], cmp[{I_, J_}], arc);
                add_edge(cmp[{I, J}], cmp[{I__, J__}], arc);
                add_edge(cmp[{_I, _J}], cmp[{I_, J_}], arc);
                add_edge(cmp[{_I, _J}], cmp[{I__, J__}], arc);
            }
        }
    }   
    // FOR(0, sz -1 , i){
    //     cout << revcmp[i].fi << " " << revcmp[i].se << "->\n";
    //     for(auto x : adj[i]){
    //         cout << "(" << revcmp[x.fi].fi << " " << revcmp[x.fi].se
    //              << " " << x.se << "), ";
    //     }
    //     cout << "\n";
    // }
    priority_queue<pair<int, double>, vector<pair<int, double>>,
    greater<pair<int, double>>>q;
    q.push({0, cmp[{0, 0}]});
    vector<double>dist(sz, 1e18);
    dist[cmp[{0, 0}]] = 0;
    while(!q.empty()){
        auto u = q.top();
        q.pop();
        if(u.fi > dist[u.se]) continue;
        for(auto v : adj[u.se]){
            if(dist[v.fi] > dist[u.se] + v.se){
                dist[v.fi] = dist[u.se] + v.se;
                q.push({dist[v.fi], v.fi});
            }
        }   
    }
    // coutAll(dist);
    cout << fixed << setprecision(20) << dist.back();




}


int main()
{
    fast_cin();    
    ll t = 1;
    // cin >> t;
    for(int it=1; it<=t; it++)
    {
        //cout << "Case " << it << ": ";
        solve(it);
    }
    return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3872kb

input:

3 5
XOOXO
OXOXO
XXXXO

output:

71.41592653589793826541

result:

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

Test #2:

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

input:

1 4
XOOX

output:

45.70796326794896913270

result:

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

Test #3:

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

input:

1 1
X

output:

20.00000000000000000000

result:

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

Test #4:

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

input:

1 1
O

output:

17.85398163397448456635

result:

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

Test #5:

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

input:

1 3
XOO

output:

35.70796326794896913270

result:

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

Test #6:

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

input:

1 5
OXOOO

output:

55.70796326794896913270

result:

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

Test #7:

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

input:

6 10
XXXXXOOOOX
XXOOOOOOOO
XXXOXOOXOX
OXOXOXXOOX
OOXXOXXXXO
OXOXXOOXOO

output:

142.83185307179587653081

result:

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

Test #8:

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

input:

1 2
XX

output:

30.00000000000000000000

result:

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

Test #9:

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

input:

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

output:

105.70796326794896913270

result:

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

Test #10:

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

input:

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

output:

214.24777960769378637451

result:

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

Test #11:

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

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

result:

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

Test #12:

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

input:

41 50
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXO
XXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXOXXXXXXXXXXXXXXX
XXXXXXXXXXXXXOXXXXXXXXXXXXXXOXXXXXXXXXX...

output:

873.51768777756626604969

result:

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

Test #13:

score: 0
Accepted
time: 789ms
memory: 141904kb

input:

329 527
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

8560.00000000000000000000

result:

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

Test #14:

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

input:

49 297
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

3451.41592653589759720489

result:

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

Test #15:

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

input:

357 83
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

4342.05750411730878113303

result:

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

Test #16:

score: 0
Accepted
time: 1343ms
memory: 213896kb

input:

417 615
XXXXXXXXOXXXXXXXXXXXOXXXXXXXXXXXOXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXOXXXXXXXXXXXXXXOXXXXXOXXXOOXXXXXXXXXXXXXXXXXXXXXOXOXXOXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXOXXXXXXOXXXXXXXXOXXXXXXXOXXXXXXXXXXXXXXXXOXXXXXXOXXXXXXXOXXXXXXXXXXOXXXXXXXXOXXXOXXXOXXXXXOXXXOXXXXXXXXXOXXXXXXXXXXXXXXXXXXXX...

output:

9736.28300444103842892218

result:

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

Test #17:

score: 0
Accepted
time: 424ms
memory: 77372kb

input:

359 225
OOOOXXOOXOXXXOOOOOXOXOOOXOOXXXXXOOOXOXXXOOOOXXOXXOOXOXOXXOXOXXXOXXXXXOOOXXXXXXXOOOOXXXXXOOXOXXOXOXOXXOXOXXOXOXOOOXOXXXOOXOXOXXXXOXOOXXOXXOXOXOXXOXXXOOOXXOOOXXOXXXXXOXOXOOXXOOXOXXOXXOOOOOXOXOOXXXOOXOOXOOOOXOXOOXXOOOXOOOXXXXOXX
OXOOOXXXOOXOOXOOXXOOXXOOXXOXXOOOOOXOXXOOXXXOXXXOXOOOXOOXXOOXOXXOXO...

output:

5026.65903927630461112130

result:

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

Test #18:

score: 0
Accepted
time: 659ms
memory: 117172kb

input:

261 431
OOOOOOOXOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOOXOOOOOOXOOOXXOOOOOOOOOOOOOOXOOXOOOOOOXOOOOOOOOOXOOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOXOXOOOOOOOOOOOOOXOOOXOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOOOOXOOOOOOOOOXXOOXOOOOOOOOOOOXOOXOOOOXOXXOOOOOOOOOOXOXOOOOOOOOOOOOOXOOOOOOOOOOOOOXOOOOOOOOXOOOOOOOOOOO...

output:

5799.77841293463643523864

result:

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

Test #19:

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

input:

37 427
OOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

4481.19464091410554829054

result:

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

Test #20:

score: 0
Accepted
time: 230ms
memory: 50196kb

input:

105 430
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

4899.33614313462385325693

result:

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

Test #21:

score: 0
Accepted
time: 1369ms
memory: 235964kb

input:

465 484
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

7494.20291959620044508483

result:

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

Test #22:

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

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

result:

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

Test #23:

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

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

result:

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

Test #24:

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

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

result:

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

Test #25:

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

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

result:

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

Test #26:

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

input:

4 204
OXOOXXXOOOXOOXXOXOXXXXOXXXXOXXXOXXOXXOXOOXOOOOXXXOXOXXXOXOOOOOXOXXXOOXOXXXXOXOOXXXOXOXOXXXOXOXXOOOXOOOXOXXXOXOOXXOOXOOOOOXOOOOOOXOXOXXOOOXXXXOOOXOOOXOOOOXXOXXOOXOXXOXOOXOOXXXOOXXOOXXXXOOOXOXXXXOOXXOOOOXXO
OXXXXXOOXOOXOXOOXOXOOOOXXOXOOOOOXOOOXOOOXOXXXOXXOXXXOOXOOXXXXXOXOXXXXXXOOXXOXXXXXOXOXOOXO...

output:

2062.83185307179519440979

result:

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

Test #27:

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

input:

4 164
XXXXXXXXXXXXOXXXXOXXXXXXXXXXXXXXXXXXXXXXOXOXOOXOXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXOXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXOXXXXXXXXXXXXXXXXOXXXO
XXXOXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXOXXXXXXXXXXXXOOXXXXXXOXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXOXXX...

output:

1662.83185307179564915714

result:

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

Test #28:

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

input:

10 243
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

2514.97787143782124985592

result:

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

Test #29:

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

input:

7 478
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

4847.85398163397439930122

result:

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

Test #30:

score: 0
Accepted
time: 890ms
memory: 149900kb

input:

400 400
OOOXXOXOXXXXXOXOXXOOXXXXOOXXXOXXOOXOXOOXOXOOOXXOXXOOOOXXOXOOXOXOXOXXXOOXOXOOXOOXXXOXXXXXXOOXXXXOXOXXXOOXOXOXXOOOOXXXXXOOXXXXXXXOOOXOXXXOXXOOOOXXOXXOXXOOOOXXOXOXOOXXOOXXXOOXOOOXXXXXXOOOXXOXOXOXOOOXOXOXXXXXXXXOXOOOXOXXOOXOXXXXOOXXXXXXOXOOXXXOXOOOOOXOXXOXXXXOOOXXOXOOOXOXOOOOXXXXOXXOXOOOOXOOXOXO...

output:

6823.98193541797809302807

result:

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

Test #31:

score: 0
Accepted
time: 958ms
memory: 168780kb

input:

400 400
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

6285.33132554555686510867

result:

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

Test #32:

score: 0
Accepted
time: 720ms
memory: 131240kb

input:

400 400
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

8000.00000000000000000000

result:

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

Test #33:

score: 0
Accepted
time: 743ms
memory: 131760kb

input:

400 400
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXX...

output:

7854.07075111025915248320

result:

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

Test #34:

score: 0
Accepted
time: 951ms
memory: 160976kb

input:

400 400
OOOOOOOXOOOOXOOOOXOXOOOOOOXOOOOOOOXOOOOOOOOOOXOOOOXOOOXOOXOOOOOOOOOOOXOOXOXOOOOOOOOOOOOOOXOOXXOXOOOOOOXOXOOOXOOOOOOOXXOOOXOOOXOXOOOOXOOOOOOOOOOOXXOXOOOXXOOOOOOOOOOOOXOOOOXOOOXOOXOOOXOOOOOXXOOOXOOOOOOOOOOOOOOXOOOOOOOXXOOOOXXOOOOOOOOXOOOOOXOOOXOOXOOOOOOOOXOOOOOOXOOOOOOOOXOXOOOOOXXOOOOOOOOOXXXO...

output:

6478.47297848785910900915

result:

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

Test #35:

score: 0
Accepted
time: 3194ms
memory: 451992kb

input:

700 700
XXXOXOXOXOOXOOXXXOOOOOXXXXOXOXOOXXOXXXOOOOOXXOXOXXXXOOOXXOXXXOXXXXXOXXXOOXXOOXOOXOXXOOXXXOOOXOOOOXXOXOOXOOXXOOXOOOXXXXOXOXOXOOOXOOXOOXXOOOXOOXOOOOXXXXXXOOXOOXXXOOOOXOOXOOXOXOOOOXOXOOXXXOXXOXOXOXXXXXOXXOOOOXXXOXOXXXOXXXXOOOXXXOXXOXXOXOOOOOOXOXOXOXXXXOXXOXXOXXOOOXXOOXOXXXOXOXOOOXOOXOOOOXOOOOOO...

output:

11922.65422168722579954192

result:

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

Test #36:

score: 0
Accepted
time: 3587ms
memory: 509600kb

input:

700 700
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

10997.72030593019735533744

result:

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

Test #37:

score: 0
Accepted
time: 2615ms
memory: 394860kb

input:

700 700
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

14000.00000000000000000000

result:

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

Test #38:

score: 0
Accepted
time: 2586ms
memory: 395820kb

input:

700 700
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

13725.30964914872311055660

result:

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

Test #39:

score: 0
Accepted
time: 3513ms
memory: 485876kb

input:

700 700
OXOXOXXOOXOOOOXOOOXOOOOOOOOOOOXOXOOOOOOOOOOXXOOOOXOXXOOOOOOOOOXOOOOOOOXOOOOOOOXOXXOOOOOOOXOOOOOOOOOOOXOOOOOOOOXOOOOOXOOOOOXOOOOXOXOOXOOOOOOXOOOXXOXOOOOOOOOOOOOXXOOOOOOOXOOOXOOOXOOOOXOOOOOOOOXOOOOOOXOOOOOXOXXXOOOOOOOOXXOOOOXOOOOOOXXXOOOOOXOOOOOOOXOOOOXOXXOOOOOXOOOOOOXXXXOOOXOOOOOOOOOOXXOXXXOO...

output:

11334.64518939621484605595

result:

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

Test #40:

score: 0
Accepted
time: 1448ms
memory: 228892kb

input:

573 492
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

9355.95092528656823560596

result:

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

Test #41:

score: 0
Accepted
time: 200ms
memory: 42128kb

input:

139 271
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
XOOOOOOOOOOOOOOOOOOO...

output:

3503.40689424488300574012

result:

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

Test #42:

score: 0
Accepted
time: 318ms
memory: 61548kb

input:

150 484
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOOOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

6335.70796326794879860245

result:

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

Test #43:

score: 0
Accepted
time: 890ms
memory: 157300kb

input:

484 308
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

6598.05268652822996955365

result:

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

Test #44:

score: 0
Accepted
time: 532ms
memory: 98536kb

input:

375 317
OXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

6173.18560862309732328868

result:

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

Test #45:

score: 0
Accepted
time: 983ms
memory: 173724kb

input:

285 578
OOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

7406.76953136540760169737

result:

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

Test #46:

score: 0
Accepted
time: 474ms
memory: 91560kb

input:

359 307
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

6655.70796326794879860245

result:

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

Test #47:

score: 0
Accepted
time: 332ms
memory: 66148kb

input:

172 354
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

4521.76968208719335962087

result:

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

Test #48:

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

input:

116 181
XOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXOOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

2658.82733692629471988766

result:

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

Test #49:

score: 0
Accepted
time: 980ms
memory: 169972kb

input:

262 615
XXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

7645.48637620258523384109

result:

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

Test #50:

score: 0
Accepted
time: 685ms
memory: 122628kb

input:

286 520
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOOXXXXXXXXXXXXXXXXXXXXXXXX...

output:

8055.70796326794879860245

result:

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

Test #51:

score: 0
Accepted
time: 997ms
memory: 174128kb

input:

675 245
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

8148.45100064745565759949

result:

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

Test #52:

score: 0
Accepted
time: 354ms
memory: 68120kb

input:

166 488
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

6136.54854718719343509292

result:

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

Test #53:

score: 0
Accepted
time: 2062ms
memory: 328180kb

input:

613 513
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

9058.18515645773368305527

result:

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

Test #54:

score: 0
Accepted
time: 1449ms
memory: 233308kb

input:

625 460
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

10845.70796326794879860245

result:

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

Test #55:

score: 0
Accepted
time: 1997ms
memory: 324572kb

input:

515 604
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

output:

8979.60108299363309924956

result:

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

Test #56:

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

input:

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

output:

217.85398163397448456635

result:

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

Test #57:

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

input:

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

output:

217.85398163397448456635

result:

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

Test #58:

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

input:

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

output:

217.85398163397448456635

result:

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

Test #59:

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

input:

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

output:

211.41592653589793826541

result:

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

Test #60:

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

input:

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

output:

194.24777960769381479622

result:

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

Test #61:

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

input:

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

output:

215.70796326794896913270

result:

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

Test #62:

score: 0
Accepted
time: 1848ms
memory: 286212kb

input:

640 552
OOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

10413.49510705003558541648

result:

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

Test #63:

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

input:

415 230
XOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXX
XXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXX...

output:

5840.53078404873667750508

result:

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

Test #64:

score: 0
Accepted
time: 1076ms
memory: 187836kb

input:

446 514
OXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

8421.83591705195249232929

result:

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

Test #65:

score: 0
Accepted
time: 783ms
memory: 138548kb

input:

436 381
XXOOOOOXXXXXXXXXXOXXXXOXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXOXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXOXXXXXXXXXXXXXXXOXXXXXXXXXXOXXOOXXXOOXXOXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXOXXXXOXXXXOXXXXXXXXXXXXXXXXX...

output:

7139.91118430771803105017

result:

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

Test #66:

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

input:

200 258
XOXXXXXXXXOXXXXXXOXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXOXXXXXXXXXXXXXXXXOXXOXXXXXOXOXOXXXXXOXXXXXXXOXXXXOXXXXXXXXXXXXXXOXXXXXXXXOOXXXXXXXXXXXXXXOXXXXXXXXXXOXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXOXXXXXXXXXXXXOOXXXXXXXXXXXOXXXXXXXXXXOXXXXXXXXXXXXXXX
XOOOXOXXXXXXXXXXXXXXXXXXXXXXXXXOX...

output:

4041.34939012758059107000

result:

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

Test #67:

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

input:

3 3
XXO
XXX
XXX

output:

57.85398163397448456635

result:

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

Test #68:

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

input:

3 3
XXX
XXX
OXX

output:

57.85398163397448456635

result:

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

Test #69:

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

input:

3 3
XXX
OXX
XXX

output:

57.85398163397448456635

result:

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

Test #70:

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

input:

3 3
XXX
XXO
XXX

output:

57.85398163397448456635

result:

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

Test #71:

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

input:

3 3
XOX
XXX
XXX

output:

57.85398163397448456635

result:

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

Test #72:

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

input:

3 3
XXX
XXX
XOX

output:

57.85398163397448456635

result:

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

Test #73:

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

input:

3 3
XOO
XXO
XXX

output:

53.56194490192345369906

result:

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

Test #74:

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

input:

3 3
XXX
OXX
OOX

output:

53.56194490192345369906

result:

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