#include "nice_lines.h" #include<bits/stdc++.h> #pragma GCC optimize("unroll-loops,O3") using namespace std; using i64 = long long; //#define int i64 #define vi vector<int> #define vvi vector<vi> #define vb vector<bool> #define se second #define fi first #define pii pair<int, int> #define sz(x) (int)(x).size() #define double long double const double INF = 2e12; void solve(int sid, int n){ i64 lo = -INF, hi = INF, mid, a = 0, b; while(hi >= lo){ mid = lo + (hi - lo) / 2; double q1, q2; if(mid + 1 > INF){ q2 = LLONG_MAX; } else{ q2 = query(0, mid + 1); } q1 = query(0, mid); //cout << "lo: " << lo << " mid: " << mid << " hi: " << hi << " q1: " << q1 << " q2: " << q2 << "\n"; if(q1 == 0){ b = mid; break; } else if(q2 == 0){ b = mid + 1; break; } if(q1 > q2){ b = mid; lo = mid + 1; } else{ hi = mid - 1; } } int y = 0; if(b == y) y++; while(hi >= lo){ mid = lo + (hi - lo) / 2; double q1, q2; if(mid + 1 > INF){ q2 = LLONG_MAX; } else{ q2 = query(mid + 1, y); } q1 = query(mid, y); //cout << "a_lo: " << lo << " mid: " << mid << " hi: " << hi << " q1: " << q1 << " q2: " << q2 << "\n"; if(q1 == 0){ a = mid; break; } else if(q2 == 0){ a = mid + 1; break; } if(q1 > q2){ a = mid; lo = mid + 1; } else{ hi = mid - 1; } } //cout << "p1: " << "0 " << b << " p2: " << a << " " << y << "\n"; int slope = (b - y) / (0 - a); vi av, bv; av.emplace_back(slope), bv.emplace_back(b); the_lines_are(av, bv); return; }