Submission #942955

#	Time	Username	Problem	Language	Result	Execution time	Memory
942955		vjudge1	Nicelines (RMI20_nicelines)	C++17	84.01 / 100	40 ms	944 KiB

nicelines

#include "nice_lines.h"

#include <bits/stdc++.h>

using namespace std;

template <class T>
struct Point
{
    T x, y;
    Point(T _x = 0, T _y = 0)
    {
        x = _x;
        y = _y;
    }
    bool operator<(Point a) { return tie(x, y) < tie(a.x, a.y); }
    bool operator==(Point a) { return tie(x, y) == tie(a.x, a.y); }
    Point operator+(Point a) { return Point(x + a.x, y + a.y); }
    Point operator-(Point a) { return Point(x - a.x, y - a.y); }
    Point operator*(T a) { return Point(x * a, y * a); }
    Point operator/(T a) { return Point(x / a, y / a); }
    T dot(Point a) { return x * a.x + y * a.y; }
    T dot(Point a, Point b) { return (a - *this).dot(b - *this); }
    T cross(Point a) { return x * a.y - y * a.x; }
    T cross(Point a, Point b) { return (a - *this).cross(b - *this); }
    T dist2() { return x * x + y * y; }
    long double dist() { return sqrt(dist2()); }
};

const long double eps = 1e-7;
using pt = Point<long double>;

long double line_point_dist(pt a, pt b, pt c)
{
    return abs(a.cross(b, c)) / (a - b).dist();
}

mt19937 rng(177013);

long double rand(long double l, long double r)
{
    return uniform_real_distribution<long double>(l, r)(rng);
}

pair<int, int> line_from_points(pt a, pt b)
{
    long double slope = round((b.y - a.y) / (b.x - a.x));
    return {(int)(round(slope)), (int)(round(a.y - a.x * slope))};
}

void solve(int subtask_id, int N)
{
    auto f = [&](long double t) -> long double
    {
        return query(3e4, t);
    };
    vector<int> va, vb;
    auto dnc = [&](auto self, long double l, long double r, long double fl, long double fr)
    {
        long double mid = (l + r) / 2;
        long double fmid = f(mid);
        if (abs((fl + fr) / 2 - fmid) < eps)
            return;
        if ((r - l) < 1)
        {
            long double c = (f(r + 0.1) - fr - fl + f(l - 0.1)) / 2;
            long double d = sqrtl(max<long double>(0.0, 0.1 * 0.1 - c * c));
            int a = round(d / c);
            if (mid < -eps)
                a = -a;
            int b = round(mid - (3e4) * a);
            va.push_back(a);
            vb.push_back(b);
            return;
        }
        self(self, l, mid, fl, fmid);
        self(self, mid, r, fmid, fr);
        return;
    };
    long double l = -3e8 - 2e4 + rand(1, 10), r = 3e8 + 2e4 - rand(1, 10);
    dnc(dnc, l, r, f(l), f(r));
    the_lines_are(va, vb);
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 13.8909043548 / 19
• Subtask 5: 21.022306730300002 / 23
• Subtask 6: 18.0934882272 / 27