#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
int least=int(sqrt(N*N*0.04));
q.push(make_tuple((N+1)/2,(N+1)/2,1,N+1,1,N+1));
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();
//cout<<x<<' '<<y<<'\n';
if(grid[x][y]==-1&&inside_shape(x,y)){
grid[x][y]=1;
return make_pair(x,y);
}
grid[x][y]=0;
if(x1-x0<=least||y1-y0<=least){
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+1;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';
if(c.first==-1){
return 0;
}
//cout<<q<<'\n';
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;
}
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;
}
}
if(ipos<N&&inside_shape(ipos+1,c.second)){
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;
}
}
if((ineg>0&&!inside_shape(ineg,c.second))||ineg==0){
ineg++;
}
//y
int found=0;
for(righty=c.second+1;righty<=N;righty++){
for(int bruh=ineg;bruh<=ipos;bruh++){
if(grid[bruh][righty]==0){
found=1;
break;
}
}
if(found==1){
break;
}
}
if(righty>N){
righty=N;
}
found=0;
for(lefty=c.second-1;lefty>0;lefty--){
for(int bruh=ineg;bruh<=ipos;bruh++){
if(grid[bruh][lefty]==0){
found=1;
break;
}
}
if(found==1){
break;
}
}
if(lefty==0){
lefty=1;
}
if((righty-lefty)<(ipos-ineg)){
return 0;
}
yo=c.second;
while(true){
jpos=(yo+righty)/2;
if(yo==jpos){
break;
}
if(inside_shape(c.first,jpos)){
yo=jpos;
}
else{
righty=jpos;
}
}
if(jpos<N&&inside_shape(c.first,jpos+1)){
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;
}
}
if((jneg>0&&!inside_shape(c.first,jneg))||jneg==0){
jneg++;
}
iwidth=ipos-ineg;
jwidth=jpos-jneg;
//cout<<ineg<<' '<<ipos<<'\n';
//cout<<jneg<<' '<<jpos<<'\n';
if(iwidth==jwidth){
return 1;
}
else{
return 0;
}
}
