This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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)1e4 + 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;
int A = (lef - B) / X;
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);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |