#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;
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);
//cout<<"Coord C:"<<c.first<<' '<<c.second<<'\n';
for(ipos=c.first+1;ipos<=N&&inside_shape(ipos,c.second);ipos++);
for(ineg=c.first-1;ineg>0&&inside_shape(ineg,c.second);ineg--);
for(jpos=c.second+1;jpos<=N&&inside_shape(c.first,jpos);jpos++);
for(jneg=c.second-1;jneg>0&&inside_shape(c.first,jneg);jneg--);
ipos--;
ineg++;
jpos--;
jneg++;
iwidth=ipos-ineg;
jwidth=jpos-jneg;
if(iwidth==jwidth){
return 1;
}
else{
return 0;
}
}
