# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1225819 | mariamtsagareli | Square or Rectangle? (NOI19_squarerect) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
extern bool inside_shape(int,int);
bool am_i_square(int n,int q){
int i,j,x1,x2,y1,y2,x0,y0,l,h,m;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(inside_shape(i,j)){
x0=i; y0=j; goto f;
}
f:
l=1; h=x0;
while(l<h){
m=(l+h)/2;
if(inside_shape(m,y0)) h=m;
else l=m+1;
}
x1=l;
l=x0; h=n;
while(l<h){
m=(l+h+1)/2;
if(inside_shape(m,y0)) l=m;
else h=m-1;
}
x2=l;
l=1; h=y0;
while(l<h){
m=(l+h)/2;
if(inside_shape(x0,m)) h=m;
else l=m+1;
}
y1=l;
l=y0; h=n;
while(l<h){
m=(l+h+1)/2;
if(inside_shape(x0,m)) l=m;
else h=m-1;
}
y2=l;
return (x2-x1)==(y2-y1);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int t,n,q;
cin>>t>>n>>q;
while(t--){
bool r=am_i_square(n,q);
cout<<(r?"YES":"NO")<<"\n";
}
return 0;
}