#include "squarerect.h"
#include <bits/stdc++.h>
using namespace std;
bool am_i_square(int N, int Q) {
int min_fill = (N * N + 24) / 25;
int min_side = std::ceil(std::sqrt(min_fill));
int x = N, y = N;
for (int i = min_side; i <= N; i += min_side) {
for (int j = min_side; j <= N; j += min_side) {
if (N < i + min_side && N < j + min_side)
continue;
if (inside_shape(i, j)) {
x = i, y = j;
goto found;
}
}
}
found:
int lo, hi;
lo = x - min_side + 1, hi = x;
while (lo < hi) {
int mi = lo + (hi - lo) / 2;
if (inside_shape(mi, y)) {
hi = mi;
} else {
lo = mi + 1;
}
}
x = lo;
lo = y - min_side + 1, hi = y;
while (lo < hi) {
int mi = lo + (hi - lo) / 2;
if (inside_shape(x, mi)) {
hi = mi;
} else {
lo = mi + 1;
}
}
y = lo;
lo = min_side + 1, hi = std::min(N - x, N - y) + 1;
while (lo < hi) {
int mi = lo + (hi - lo) / 2;
if (!inside_shape(x + mi, y + mi)) {
hi = mi;
} else {
lo = mi + 1;
}
}
int side = lo - 1;
bool valid = true;
if (x + side + 1 <= N && y + side <= N)
valid &= !inside_shape(x + side + 1, y + side);
if (x + side <= N && y + side + 1 <= N)
valid &= !inside_shape(x + side, y + side + 1);
return valid;
}
