#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, m1, m2; i64 a = INF + 1, b = INF + 1; while(hi > lo){ m1 = lo + (hi - lo) / 3; m2 = hi - (hi - lo) / 3; double q1 = query(0, m1), q2 = query(0, m2); if(q1 == q2){ b = m1; break; } if(q1 > q2){ lo = m1 + 1; } else{ hi = m2 - 1; } } if(b > INF){ for(int i = max(-INF, (double)(lo - 3)); i <= min(INF, (double)(hi + 3)); i++){ if(query(0, i) == 0){ b = i; break; } } } int y = 1; if(y == b) y++; lo = -INF, hi = INF; while(hi > lo){ m1 = lo + (hi - lo) / 3; m2 = hi - (hi - lo) / 3; double q1 = query(m1, y), q2 = query(m2, y); if(q1 == q2){ a = m1; break; } if(q1 > q2){ lo = m1 + 1; } else{ hi = m2 - 1; } } if(a > INF){ for(int i = max(-INF, (double)(lo - 3)); i <= min(INF, (double)(hi + 3)); i++){ if(query(i, y) == 0){ a = i; break; } } } // p1 = {0, b}, p2 = {a, y} int slope = (y - b) / (a - 0); vi av, bv; av.emplace_back(slope), bv.emplace_back(b); the_lines_are(av, bv); return; }