Submission #944378

#TimeUsernameProblemLanguageResultExecution timeMemory
944378marvinthangNicelines (RMI20_nicelines)C++17
31 / 100
99 ms2604 KiB
/************************************* * author: marvinthang * * created: 11.03.2024 09:22:47 * *************************************/ #include "nice_lines.h" #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define left ___left #define right ___right #define TIME (1.0 * clock() / CLOCKS_PER_SEC) #define MASK(i) (1LL << (i)) #define BIT(x, i) ((x) >> (i) & 1) #define __builtin_popcount __builtin_popcountll #define ALL(v) (v).begin(), (v).end() #define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i) #define REPD(i, n) for (int i = (n); i-- > 0; ) #define FOR(i, a, b) for (int i = (a), _b = (b); i < _b; ++i) #define FORD(i, b, a) for (int i = (b), _a = (a); --i >= _a; ) #define FORE(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i) #define FORDE(i, b, a) for (int i = (b), _a = (a); i >= _a; --i) #define scan_op(...) istream & operator >> (istream &in, __VA_ARGS__ &u) #define print_op(...) ostream & operator << (ostream &out, const __VA_ARGS__ &u) #ifdef LOCAL #include "debug.h" #else #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } #define DB(...) 23 #define db(...) 23 #define debug(...) 23 #endif template <class U, class V> scan_op(pair <U, V>) { return in >> u.first >> u.second; } template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; } template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.first << ", " << u.second << ')'; } template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")"; else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); } template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); } template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; } // end of template #define double long double const double EPS = 1e-8; const int MAX_C = 1e4 + 5; const int PX = MAX_C * 2 + 1; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); template <class T> T rand(T l, T h) { return uniform_int_distribution <T> (l, h) (rng); } template <class T> T rand(T h) { return uniform_int_distribution <T> (0, h - 1) (rng); } struct Point { int x; double y; Point(int x = 0, double y = 0): x(x), y(y) {} }; struct Line { Point m, n; double a, b; Line(const Point &_m, const Point &_n) { m = _m; n = _n; a = (m.y - n.y) / (m.x - n.x); b = m.y - a * m.x; } int intersectX(const Line &ot) const { return round((ot.b - b) / (a - ot.a)); } double get_val(double x) const { return x * a + b; } }; void solve(int subtask_id, int n) { auto collinear = [&] (const Point &a, const Point &b, const Point &c) { return abs((b.x - a.x) / (b.y - a.y) - (c.x - a.x) / (c.y - a.y)) <= EPS; }; auto getP = [&] (int x) { return Point(x, query(PX, x)); }; vector <int> aa, bb; auto solve = [&] (auto &&solve, const Line &left, const Line &right) { if ((int) aa.size() == n) return; if (abs(left.a - right.a) <= EPS) return; int m = left.intersectX(right); Point mid = getP(m); if (collinear(left.m, left.n, mid) && collinear(right.m, right.n, mid)) { int b = m % PX; if (b < 0) b += PX; if (b > MAX_C) b -= PX; aa.push_back((m - b) / PX); bb.push_back(b); return; } Line ml(mid, getP(m + 1)); solve(solve, left, ml); solve(solve, ml, right); }; int r = PX * MAX_C + MAX_C; int l = -r; solve(solve, Line(getP(l), getP(l + 1)), Line(getP(r), getP(r + 1))); the_lines_are(aa, bb); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...