Submission #47537

#	Time	Username	Problem	Language	Result	Execution time	Memory
47537		tieunhi	Experiments with Gorlum (IZhO13_expgorl)	C++14	100 / 100	9 ms	1088 KiB

expgorl

#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 (stderr)

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++)
                     ~~^~~~~~~~~~

• Subtask 1: 100 / 100