Submission #493572

#	Time	Username	Problem	Language	Result	Execution time	Memory
493572		Jeff12345121	Nicelines (RMI20_nicelines)	C++14	11 / 100	5 ms	288 KiB

nicelines

#include <bits/stdc++.h>
using namespace std;
#include "nice_lines.h"



const long long MAXVAL = 1000000000005;
const long double LIMIT = 0.00001;

int n;

long double dis (long double x, long double y, long double m , long double k) {
    long double k2 = y + m * x;
    long double Yi = (k + k2) / 2;
    long double Xi = ( k2 - k ) / 2 * m;
    return sqrt( (x - Xi) * (x - Xi) + (y - Yi) * (y - Yi) );
};

bool dEqual(long double x, long double y) {
    if (x > y) {
        return x - y < LIMIT;
    }
    return y - x < LIMIT;
}
long long tern_search(long long x) {
    long long l = -MAXVAL, r = MAXVAL;
    while (l <= r) {
        long long dif = r - l + 1;
        long long left_third = l + dif / 3;
        long long right_third = l + dif * 2 / 3;
        long double fLeft = query(x , left_third);
        long double fRight = query(x , right_third);
        if (fLeft == 0) {
            return left_third;
        }
        if (fRight == 0) {
            return right_third;
        }
        if (dEqual(fLeft , fRight)) {
            l = left_third + 1;
            r = right_third - 1;
        } else if (fLeft > fRight) {
            l = left_third + 1;
        } else {
            r = right_third - 1;
        }
    }
    return 0;
}
void solve(int subtask_id, int N) {
    n = N;
    long long y1 = tern_search(0);
    long long y2 = tern_search(1);
    int k = y1, m = y2 - y1;
    the_lines_are({m}, {k});
}
/*
int main() {
    int n;
    a.resize(n);
    b.resize(n);
    in >> n;
    for (int i = 0; i < n; i++) {
        in >> a[i] >> b[i];
    }
    solve(1 , n);
}
*/

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