#include "squarerect.h"
#include <bits/stdc++.h>
using namespace std;
bool am_i_square(int N, int Q) {
int used = 0;
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 < i; j += min_side) {
if (used++, inside_shape(i, j)) {
x = i, y = j;
goto found;
}
if (used++, inside_shape(j, i)) {
x = j, y = i;
goto found;
}
}
if (N < i + min_side)
goto found;
if (used++, inside_shape(i, i)) {
x = i, y = i;
goto found;
}
}
found:
int lo, hi;
lo = x - min_side + 1, hi = x;
while (lo < hi) {
int mi = lo + (hi - lo) / 2;
if (used++, 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 (used++, inside_shape(x, mi)) {
hi = mi;
} else {
lo = mi + 1;
}
}
y = lo;
if (N < x + min_side - 1 || N < y + min_side - 1)
return false;
lo = min_side - 1, hi = std::min(N - x, N - y) + 1;
while (lo < hi) {
int mi = lo + (hi - lo) / 2;
if (used++, !inside_shape(x + mi, y + mi)) {
hi = mi;
} else {
lo = mi + 1;
}
}
int side = lo;
bool valid = side != min_side - 1;
if (valid && x + side - 1 <= N && y + side <= N)
valid &= !inside_shape(x + side - 1, y + side);
if (valid && x + side <= N && y + side - 1 <= N)
valid &= !inside_shape(x + side, y + side - 1);
return valid;
}
