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)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;
int nn;
void solve(int lef, int rig, ld la, ld ra){
if(aa.size() == nn) return;
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;
if(rand() % 2 == 0){
solve(lef, mid, la, ma);
solve(mid + 1, rig, ma, ra);
}
else{
solve(mid + 1, rig, ma, ra);
solve(lef, mid, la, ma);
}
}
void solve(int subtask_id, int N) {
nn = 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);
}
Compilation message (stderr)
nicelines.cpp: In function 'void solve(int, int, ld, ld)':
nicelines.cpp:25:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
25 | if(aa.size() == nn) return;
| ~~~~~~~~~~^~~~~
# | 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... |