oj.uz

Submission #493572

# Submission time Handle Problem Language Result Execution time Memory
493572 2021-12-12T08:31:27 Z Jeff12345121 Nicelines (RMI20_nicelines) C++14
11 / 100
 5 ms 288 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 264 KB Output is correct
2 Correct 5 ms 200 KB Output is correct
3 Correct 4 ms 200 KB Output is correct
4 Correct 5 ms 200 KB Output is correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 288 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -