This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/
#include "nice_lines.h"
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define pb push_back
#define ff first
#define ss second
#define isz(x) (int)x.size()
using namespace std;
const int mxC = 2e4;
const int EmptyLow = mxC + 1;
const int EmptyHigh = 2 * mxC - 1;
const int mod = 3 * mxC;
const long double eps = 1e-4;
struct Point {
long double x, y;
Point(long double x, long double y) : x(x), y(y) {}
friend ostream & operator << (ostream &out, const Point &p) {
return out << "{" << p.x << ", " << p.y << "}" << endl;
}
};
struct Line {
long double a, b;
Line(long double a, long double b) : a(a), b(b) {}
Line(Point p, Point q) {
a = (q.y - p.y) / (q.x - p.x);
b = p.y - a * p.x;
}
bool OnLine(Point p) {
return abs(a * p.x + b - p.y) < eps;
}
friend ostream & operator << (ostream &out, const Line &l) {
return out << l.a << "x + " << l.b;
}
};
Point intersectLines(const Line& l1, const Line& l2) {
long double x = (l2.b - l1.b) / (l1.a - l2.a);
long double y = l1.a * x + l1.b;
return Point(x, y);
}
int cnt;
// long double query(long double x, long double y) { return 0.0L; }
long double F(long double x) { return query(mod, x); }
set<i64> res;
void dnc(Line ll, Line lr) {
// if (++cnt >= 5) return;
// cout << ll << endl << lr << endl;
// cout << ll << " " << lr << endl;
auto inter = intersectLines(ll, lr);
i64 y = round(inter.x);
// cout << y << endl;
// return;
i64 rem = (y % mod + mod) % mod;
// cout << rem << endl;
if (EmptyLow <= rem and rem <= EmptyHigh) {
i64 d1 = y - (rem - EmptyLow);
i64 d2 = y + (EmptyHigh - rem);
Line lm(Point(d1, F(d1)), Point(d2, F(d2)));
dnc(ll, lm); dnc(lm, lr);
return;
}
i64 u1 = (rem < EmptyLow ? y + EmptyLow - rem : y + mod + EmptyLow - rem);
i64 u2 = (rem < EmptyHigh ? y + EmptyHigh - rem : y + mod + EmptyHigh - rem);
i64 d1 = u1 - mod, d2 = u2 - mod;
// cout << d1 << " " << u1 << " " << d2 << " " << u2 << endl;
// return;
Point Fd2 = Point(d2, F(d2));
// cout << Fd2 << endl;
if (ll.OnLine(Fd2)) {
Point Fu1 = Point(u1, F(u1));
// cout << Fu1 << endl;
// return;
if (lr.OnLine(Fu1)) res.insert(y);
else dnc(Line(Fu1, Point(u2, F(u2))), lr);
}
else {
// cout << "trolled" << endl;
// return;
Line lm = Line(Point(d1, F(d1)), Fd2);
// cout << lm << endl;
dnc(ll, lm); dnc(lm, lr);
}
}
void solve(int subtask_id, int n) {
cout << fixed << setprecision(12);
i64 l1 = -1ll * mod * mod - EmptyHigh;
// cout << F(l2) << endl;
i64 l2 = -1ll * mod * mod - EmptyLow;
i64 r1 = 1ll * mod * mod + EmptyLow;
i64 r2 = 1ll * mod * mod + EmptyHigh;
dnc(Line(Point(l1, F(l1)), Point(l2, F(l2))), Line(Point(r1, F(r1)), Point(r2, F(r2))));
// dnc(Line(-1.451158241278, 240305.953013565319), Line(-1.442833588481, 480305.954147797289));
// long long lowY1 = -1LL * MaxX * MaxX - Rest2;
// long double lowVal1 = query(MaxX, lowY1);
// long long lowY2 = -1LL * MaxX * MaxX - Rest1;
// long double lowVal2 = query(MaxX, lowY2);
// Line lowLine(lowY1, lowVal1, lowY2, lowVal2);
// long long highY1 = 1LL * MaxX * MaxX + Rest1;
// long double highVal1 = query(MaxX, highY1);
// long long highY2 = 1LL * MaxX * MaxX + Rest2;
// long double highVal2 = query(MaxX, highY2);
// Line highLine(highY1, highVal1, highY2, highVal2);
// divide(lowLine, highLine);
vector<int> a, b;
for (auto y : res) {
i64 bb = y % mod;
if (bb < -mxC) bb += mod;
if (bb > mxC) bb -= mod;
i64 aa = (y - bb) / mod;
a.push_back(aa);
b.push_back(bb);
}
the_lines_are(a, b);
}
// int main() {
// cout << -1 << endl;
// }
# | 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... |