| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1220845 | mariamtsagareli | Square or Rectangle? (NOI19_squarerect) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int X1,Y1,X2,Y2,N,Q,qc;
bool inside_shape(int x,int y){
qc++;
return x>=X1&&x<=X2&&y>=Y1&&y<=Y2;
}
bool am_i_square(int n,int q){
if(q>50){
int i=0,x=-1,y=-1;
srand(74231);
while(i<q/2){
int a=rand()%n+1,b=rand()%n+1;
if(inside_shape(a,b)){x=a;y=b;break;}
i++;
}
if(x<0){
for(int a=1;a<=n&&i<q/2;a+=5)
for(int b=1;b<=n&&i<q/2;b+=5){
if(inside_shape(a,b)){x=a;y=b;break;}
i++;
}
}
if(x<0)x=y=1;
int l=x,r=x,u=y,d=y;
while(i<q&&l>1){
if(inside_shape(l-1,y))l--;else break;
i++;
}
while(i<q&&r<n){
if(inside_shape(r+1,y))r++;else break;
i++;
}
while(i<q&&u>1){
if(inside_shape(x,u-1))u--;else break;
i++;
}
while(i<q&&d<n){
if(inside_shape(x,d+1))d++;else break;
i++;
}
return (r-l)==(d-u);
} else {
int c=(n+1)/2,s=(n+10)/11,p=c,o=c;
for(int i=1;i<=10;i++){
int t=i*s;
if(t>n)t=n;
if(inside_shape(c,t)){p=c;o=t;break;}
}
int l=1,r=p,m;
while(l<r){
m=(l+r)/2;
if(inside_shape(m,o))r=m;else l=m+1;
}
int f=l;
l=p;r=n;
while(l<r){
m=(l+r+1)/2;
if(inside_shape(m,o))l=m;else r=m-1;
}
int g=l;
int u=1,d=o;
l=1;r=o;
while(l<r){
m=(l+r)/2;
if(inside_shape(p,m))r=m;else l=m+1;
}
int h=l;
l=o;r=n;
while(l<r){
m=(l+r+1)/2;
if(inside_shape(p,m))l=m;else r=m-1;
}
int k=l;
return (g-f)==(k-h);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin>>T>>N>>Q;
for(int t=0;t<T;t++){
cin>>X1>>Y1>>X2>>Y2;
qc=0;
bool sq=am_i_square(N,Q);
cout<<(sq?"square\n":"rectangle\n");
}
return 0;
}