oj.uz

답안 #349031

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
349031 2021-01-16T11:15:46 Z nicolaalexandra 생물 실험 (IZhO13_expgorl) C++14
0 / 100
 1 ms 492 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>>xstart>>ystart>>x>>y;

    v[1] = make_pair (xstart,ystart);
    int el = 1;
    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);
    }

    n = el;

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

        double maxi = 0, mini = INF;
        check_points (1,maxi,0);
        check_points (1,mini,1);

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

        return 0;
    }



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


    /// punctele de start
    w[1] = make_pair(xstart,ystart);
    for (i=2;i<=k;i++)
        w[i] = make_pair(w[i-1].first + add_x, w[i-1].second + add_y);


    /// distanta maxima
    double maxi = 0;
    check_points (1,maxi,0);
    check_points (k,maxi,0);


    /// distanta minima
    int st = 1, dr = k-1;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (get_dist(w[mid].first,w[mid].second,x,y) > get_dist(w[mid+1].first,w[mid+1].second,x,y))
            st = mid+1;
        else dr = mid-1;
    }

    double mini = INF;

    check_points (st,mini,1);

    if (st < k)
        check_points (st+1,mini,1);
    if (st > 1)
        check_points (st-1,mini,1);

    cout<<setprecision(9)<<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
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -