Submission #750830

#	Time	Username	Problem	Language	Result	Execution time	Memory
750830		doowey	Nicelines (RMI20_nicelines)	C++14	82.63 / 100	66 ms	320 KiB

nicelines

#include <bits/stdc++.h>
#include "nice_lines.h"

using namespace std;

typedef long double ld;
typedef pair<ld, ld> pdd;

#define fi first
#define se second
#define mp make_pair

const int X = (int)2e4 + 4;
const int B = X * 1ll * X;
const ld EPS = 1e-5;

bool on_line(ld x0, ld y0, ld x1, ld y1, ld x2, ld y2){
    return abs((x2 - x1) * (y1 - y0) - (y2 - y1) * (x1 - x0)) < EPS;
}

vector<int> aa, bb;

void solve(int lef, int rig, ld la, ld ra){
    if(la < 0.0){
        la = query(X, (ld)lef - 0.5);
    }
    if(ra < 0.0){
        ra = query(X, (ld)rig + 0.5);
    }
    if(lef == rig){
        ld ma = query(X, lef);
        if(on_line(lef - 0.5, la, lef, ma, rig + 0.5, ra)) return;
        int B = (lef % X + X) % X;
        if(B > (int)1e4) B = -(X-B);
        int A = (lef - B) / X;
        //cout << lef << " " << A << " " << B << "\n";
        aa.push_back(A);
        bb.push_back(B);
        return;
    }
    int mid = lef + (rig - lef) / 2;
    ld ma = query(X, (ld)mid + 0.5);
    if(on_line(lef - 0.5, la, mid + 0.5, ma, rig + 0.5, ra)) return;
    solve(lef, mid, la, ma);
    solve(mid + 1, rig, ma, ra);

}

void solve(int subtask_id, int N) {
    /*
    printf("subtask_id = %d, N = %d\n", subtask_id, N);
    printf("query(0, 0) = %Lf\n", query(0, 0));
    printf("query(1, 1) = %Lf\n", query(1, 1));
    */
    solve(-B, B, -1.0, -1.0);
    the_lines_are(aa, bb);
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 12.5550843926 / 19
• Subtask 5: 21.2370181289 / 23
• Subtask 6: 17.8414357158 / 27