oj.uz

Submission #349043

# Submission time Handle Problem Language Result Execution time Memory
349043 2021-01-16T11:59:14 Z nicolaalexandra Experiments with Gorlum (IZhO13_expgorl) C++14
100 / 100
 3 ms 364 KB 
#include <bits/stdc++.h>
#define DIM 100010
#define INF 2000000000
using namespace std;

pair <int,int> v[DIM],w[DIM];
char s[DIM];
int n,k,i,add_x,add_y,x,y,xstart,ystart;


double get_dist (int x, int y, int x2, int y2){
    return sqrt (1LL * (x-x2) * (x-x2) + 1LL * (y-y2) * (y-y2));
}

void check_points(int poz, double &sol, int tip){

    for (int i=1;i<=n;i++){
        int xx = v[i].first + add_x * (poz-1);
        int yy = v[i].second + add_y * (poz-1);

        double dist = get_dist (xx,yy,x,y);
        if (!tip)
            sol = max (sol,dist);
        else sol = min (sol,dist);
    }

}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>k>>s+1;
    n = strlen (s+1);
    cin>>x>>y>>xstart>>ystart;

    v[1] = make_pair (xstart,ystart);
    int el = 1;

    double maxi = get_dist(xstart,ystart,x,y), mini = get_dist(xstart,ystart,x,y);

    for (i=1;i<=n;i++){
        if (s[i] == 'I')
            continue;
        int dx = 0, dy = 0;
        if (s[i] == 'L')
            dx = -1;
        if (s[i] == 'R')
            dx = 1;
        if (s[i] == 'F')
            dy = 1;
        if (s[i] == 'B')
            dy = -1;

        ++el;
        v[el] = make_pair(v[el-1].first + dx, v[el-1].second + dy);
        maxi = max (maxi,get_dist(v[el].first,v[el].second,x,y));
        mini = min (mini,get_dist(v[el].first,v[el].second,x,y));
    }

    n = el;

    if (v[1] == v[n]){

        cout<<setprecision(20)<<fixed<<mini<<" "<<maxi;

        return 0;
    }


    add_x = v[n].first - v[1].first;
    add_y = v[n].second - v[1].second;


    for (i=1;i<=n;i++){

        int xc = v[i].first, yc = v[i].second;

        /// verific doar capetele segmentului
        maxi = max (maxi,get_dist(xc,yc,x,y));
        maxi = max (maxi,get_dist(xc + add_x*(k-1),yc + add_y*(k-1),x,y));

        int st = 1, dr = k-1;
        while (st <= dr){
            int mid = (st+dr)>>1;

            int xx = xc + add_x * (mid-1);
            int yy = yc + add_y * (mid-1);

            if (get_dist(xx,yy,x,y) > get_dist(xx+add_x,yy+add_y,x,y))
                st = mid+1;
            else dr = mid-1;

        }

        mini = min (mini,get_dist(xc + add_x*st, yc + add_y*st, x,y));
        if (st > 1)
            mini = min (mini,get_dist(xc + add_x*(st-1), yc + add_y*(st-1), x,y));
        if (st < k)
            mini = min (mini,get_dist(xc + add_x*(st+1), yc + add_y*(st+1), x,y));
    }

    cout<<setprecision(20)<<fixed<<mini<<" "<<maxi;



    return 0;
}

Compilation message

expgorl.cpp: In function 'int main()':
expgorl.cpp:34:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     cin>>k>>s+1;
      |             ~^~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 2 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 2 ms 364 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 2 ms 364 KB Output is correct
15 Correct 2 ms 364 KB Output is correct
16 Correct 2 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 2 ms 364 KB Output is correct
19 Correct 2 ms 364 KB Output is correct
20 Correct 3 ms 364 KB Output is correct