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>
using namespace std;
typedef long long ll;
typedef long double ld;
#include "nice_lines.h"
map<ll, map<ll, ld> > cache;
ld Q(ll x, ll y){
if (cache[x].count(y)) return cache[x][y];
else return cache[x][y] = query((ld)x, (ld)y);
}
ld getdiff(ll x, ll y){
return Q(x, y+1) - Q(x, y);
}
vector<ll> ans;
vector<ld> diffs;
ll X = 20001;
void dnc(ll L, ll R, ld S, ld E){
if (abs(S-E) < 1e-10){
return;
}
///printf("DNC %lld %lld %.20Lf %.20Lf, %.20Lf\n",L,R,S,E, E-S);
if (L >= R) return;
for (auto x : diffs){
if (abs(E-S-x) < 1e-10){
///printf("FOUND %.20Lf %.20Lf = %.20Lf\n",S,E,E-S-x);
long double difff = Q(X, R) - Q(X, L) - (R-L)*S;
long double idx = difff/x;
///printf("%d diffs\n", (int)round(idx));
ans.push_back(R-(int)round(idx));
return;
}
}
if (L+1 == R){
ans.push_back(L+1);
return;
}
ll mid = (L+R)/2;
ld Q = getdiff(X, mid);
dnc(L, mid, S, Q);
dnc(mid, R, Q, E);
}
void solve(int subtask_id, int N) {
///printf("subtask_id = %d, N = %d\n", subtask_id, N);
ll L = -10000*X - 10000 - 1;
ll R = 10000*X + 10000 + 1;
for (ll i = 0; i <= 10000; i++){
long double D = (ld)(2.0)/sqrtl(i*i + 1);
///printf("%.20Lf\n",D);
diffs.push_back(D);
}
long double Q1 = getdiff(X, L);
long double Q2 = getdiff(X, R);
dnc(L, R, Q1, Q2);
vector<int> a,b;
for (auto x : ans){
///printf("%lld\n",x);
int A = round((ld)x/X);
int B = x - A*X;
a.push_back(A); b.push_back(B);
}
the_lines_are(a,b);
}
# | 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... |