#include <cmath>
#include <vector>
#include "nice_lines.h"
/*
* Алгоритм:
*
* [1] a[i] олох:
* s(t) = query(BIG, t*BIG) / BIG - known_slope_contrib(t)
* ≈ Σ |a[i]-t| / sqrt(a[i]^2+1) (b/BIG noise negligible)
* Binary search: s(mid+1) < s(mid) => lo = mid+1
*
* [2] b[i] олох (a_val мэдэгдэж байгаа):
* g(c) = query(BIG2, a_val*BIG2+c) - known_intercept_contrib(c)
* ≈ |b_target-c| / w_target + small contributions
* Binary search: g(mid+1) < g(mid) => lo = mid+1
*
* Query тоо: N * 2 * 15 * 2 = N*60, N=100 => 6000 < 10000 ✓
* BIG = 1e8: t*BIG <= 10000*1e8 = 1e12 ✓
* BIG2 = 1e4: a_val*BIG2+c <= 10000*1e4+10000 ≈ 1e8 << 1e12 ✓
*/
static const long double BIG = 1e8L;
static const long double BIG2 = 1e4L;
static long double slope_val(long double t,
const std::vector<int>& ka,
const std::vector<int>& kb)
{
long double raw = query(BIG, t * BIG) / BIG;
for (int k = 0; k < (int)ka.size(); k++) {
long double w = sqrtl((long double)ka[k]*ka[k] + 1.0L);
raw -= fabsl((long double)ka[k]*BIG - t*BIG + (long double)kb[k]) / w / BIG;
}
return raw;
}
static long double intercept_val(long double c, int a_val,
const std::vector<int>& ka,
const std::vector<int>& kb)
{
long double av = (long double)a_val;
long double raw = query(BIG2, av * BIG2 + c);
for (int k = 0; k < (int)ka.size(); k++) {
long double w = sqrtl((long double)ka[k]*ka[k] + 1.0L);
raw -= fabsl((long double)ka[k]*BIG2 - av*BIG2 - c + (long double)kb[k]) / w;
}
return raw;
}
void solve(int subtask_id, int N) {
std::vector<int> found_a, found_b;
std::vector<int> known_a, known_b;
for (int iter = 0; iter < N; iter++) {
// ── [1] a[i] олох ─────────────────────────────────────────────
int lo = -10000, hi = 10000;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
long double fl = slope_val((long double)mid, known_a, known_b);
long double fr = slope_val((long double)(mid+1), known_a, known_b);
if (fr < fl) lo = mid + 1;
else hi = mid;
}
int a_val = lo;
// ── [2] b[i] олох ─────────────────────────────────────────────
lo = -10000; hi = 10000;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
long double fl = intercept_val((long double)mid, a_val, known_a, known_b);
long double fr = intercept_val((long double)(mid+1), a_val, known_a, known_b);
if (fr < fl) lo = mid + 1;
else hi = mid;
}
int b_val = lo;
known_a.push_back(a_val);
known_b.push_back(b_val);
found_a.push_back(a_val);
found_b.push_back(b_val);
}
the_lines_are(found_a, found_b);
}
