Submission #47537

# Submission time Handle Problem Language Result Execution time Memory
47537 2018-05-05T02:57:19 Z tieunhi Experiments with Gorlum (IZhO13_expgorl) C++14
100 / 100
9 ms 1088 KB
#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define N 100005
#define maxc 1000000007

using namespace std;

using db = long double;
struct Point
{
    int x, y;
    Point operator + (Point p) const {
        return {x + p.x, y + p.y};
    }
    Point operator - (Point p) const {
        return {x - p.x, y - p.y};
    }
    Point operator * (int k) const {
        return {x*k, y*k};
    }
}laser, gorlum, delta, f[5];

int K;
vector<Point> all;
string s;
string SS = "LRFBI";

db dist(Point p, Point q)
{
    p = p - q;
    return sqrt(1ll*p.x*p.x + 1ll*p.y*p.y);
}


void setup()
{
    f[0] = {-1, 0};
    f[1] = {1, 0};
    f[2] = {0, 1};
    f[3] = {0, -1};
    f[4] = {0, 0};
    cin >> K >> s;
    cin >> laser.x >> laser.y;
    cin >> gorlum.x >> gorlum.y;
}

void solve(Point x, db &vMin, db &vMax)
{
    int L = 0, R = K-1;
    while (R - L > 2)
    {
        int M1 = L + (R - L)/3;
        int M2 = R - (R - L)/3;
        db xx = dist(x + delta*M1, laser);
        db yy = dist(x + delta*M2, laser);
        if (xx < yy)
            R = M2;
        else L = M1;
    }
    for (int i = L; i <= R; i++)
        vMin = min(vMin, dist(x + delta*i, laser));
    vMax = max(vMax, dist(x, laser));
    vMax = max(vMax, dist(x + delta*(K-1), laser));
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    setup();
    Point cur = gorlum;
    for (int i = 0; i < s.size(); i++)
    {
        all.PB(cur);
        int typeId = SS.find(s[i]);
        cur = cur + f[typeId];
    }
    delta = cur - gorlum;
    db resMax = 0, resMin = 1e15;
    for (int i = 0; i < s.size(); i++)
        solve(all[i], resMin, resMax);
    cout<<fixed<<setprecision(9)<<resMin<<" ";
    cout<<fixed<<setprecision(9)<<resMax;
}

Compilation message

expgorl.cpp: In function 'int main()':
expgorl.cpp:75:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < s.size(); i++)
                     ~~^~~~~~~~~~
expgorl.cpp:83:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < s.size(); i++)
                     ~~^~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 560 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 3 ms 560 KB Output is correct
5 Correct 3 ms 564 KB Output is correct
6 Correct 3 ms 564 KB Output is correct
7 Correct 3 ms 564 KB Output is correct
8 Correct 3 ms 756 KB Output is correct
9 Correct 6 ms 976 KB Output is correct
10 Correct 8 ms 976 KB Output is correct
11 Correct 5 ms 976 KB Output is correct
12 Correct 8 ms 1024 KB Output is correct
13 Correct 8 ms 1024 KB Output is correct
14 Correct 7 ms 1024 KB Output is correct
15 Correct 7 ms 1024 KB Output is correct
16 Correct 9 ms 1024 KB Output is correct
17 Correct 9 ms 1024 KB Output is correct
18 Correct 9 ms 1040 KB Output is correct
19 Correct 9 ms 1040 KB Output is correct
20 Correct 9 ms 1088 KB Output is correct