#include "squarerect.h"
#include <bits/stdc++.h>
using namespace std;
pair<int,int> find_first_in(int N, int grid[105][105]){
queue<tuple<int,int,int,int,int,int>> q; //x,y,x0,x1,y0,y1
q.push(make_tuple(N/2,N/2,1,N,1,N));
while(!q.empty()){
auto i=q.front();
int x=get<0>(i);
int y=get<1>(i);
int x0=get<2>(i);
int x1=get<3>(i);
int y0=get<4>(i);
int y1=get<5>(i);
q.pop();
if(inside_shape(x,y)){
grid[x][y]=1;
return make_pair(x,y);
}
grid[x][y]=0;
if(x1-x0<=1&&y1-y0<=1){
continue;
}
if(x>x0){
if(y>y0){
q.push(make_tuple((x0+x)/2,(y0+y)/2,x0,x,y0,y));
}
if(y1>y){
q.push(make_tuple((x0+x)/2,(y+y1)/2,x0,x,y,y1));
}
}
if(x1>x){
if(y>y0){
q.push(make_tuple((x+x1)/2,(y0+y)/2,x,x1,y0,y));
}
if(y1>y){
q.push(make_tuple((x+x1)/2,(y+y1)/2,x,x1,y,y1));
}
}
}
return make_pair(-1,-1);
}
bool am_i_square(int N, int Q) {
int grid[105][105],ipos,jpos,ineg,jneg,iwidth,jwidth,rightx,leftx,righty,lefty;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
grid[i][j]=-1;
}
}
auto c=find_first_in(N,grid);
for(rightx=c.first+1;rightx<=N&&grid[rightx][c.second]==-1;rightx++){
if(rightx>N){
rightx=N;
}
}
for(leftx=c.first-1;leftx>0&&grid[leftx][c.second]==-1;leftx--){
if(leftx==0){
leftx==1;
}
}
for(righty=c.second+1;righty<=N&&grid[c.first][righty]==-1;righty++){
if(righty>N){
righty=N;
}
}
for(lefty=c.second-1;lefty>0&&grid[c.first][lefty]==-1;lefty--){
if(lefty==0){
lefty==1;
}
}
//cout<<"Coord C:"<<c.first<<' '<<c.second<<'\n';
int yo=c.first;
while(true){
ipos=(yo+rightx)/2;
if(yo==ipos){
break;
}
if(inside_shape(ipos,c.second)){
yo=ipos;
}
else{
rightx=ipos;
}
}
yo=c.first;
while(true){
ineg=(yo+leftx)/2;
if(ineg==leftx){
break;
}
if(inside_shape(ineg,c.second)){
yo=ineg;
}
else{
leftx=ineg;
}
}
yo=c.second;
while(true){
jpos=(yo+righty)/2;
if(yo==jpos){
break;
}
if(inside_shape(c.first,jpos)){
yo=jpos;
}
else{
righty=jpos;
}
}
yo=c.second;
while(true){
jneg=(yo+lefty)/2;
if(jneg==lefty){
break;
}
if(inside_shape(c.first,jneg)){
yo=jneg;
}
else{
lefty=jneg;
}
}
ipos--;
ineg++;
jpos--;
jneg++;
iwidth=ipos-ineg;
jwidth=jpos-jneg;
if(iwidth==jwidth){
return 1;
}
else{
return 0;
}
}
