Red Huang

Red Huang

uva 10707

Using mathematics to record the characteristics of each point

For example, the number of points in the adjacent row and column can record the state of this point

If it originally is | and changes to an L shape

then it will be different, but the direction of rotation and the position of movement have no effect

//  
//        GGGGGGGGGGGGG        CCCCCCCCCCCCC               AAA  
//     GGG::::::::::::G     CCC::::::::::::C              A:::A  
//   GG:::::::::::::::G   CC:::::::::::::::C             A:::::A  
//  G:::::GGGGGGGG::::G  C:::::CCCCCCCC::::C            A:::::::A  
// G:::::G       GGGGGG C:::::C       CCCCCC           A:::::::::A  
//G:::::G              C:::::C                        A:::::A:::::A  
//G:::::G              C:::::C                       A:::::A A:::::A  
//G:::::G    GGGGGGGGGGC:::::C                      A:::::A   A:::::A  
//G:::::G    G::::::::GC:::::C                     A:::::A     A:::::A  
//G:::::G    GGGGG::::GC:::::C                    A:::::AAAAAAAAA:::::A  
//G:::::G        G::::GC:::::C                   A:::::::::::::::::::::A  
// G:::::G       G::::G C:::::C       CCCCCC    A:::::AAAAAAAAAAAAA:::::A  
//  G:::::GGGGGGGG::::G  C:::::CCCCCCCC::::C   A:::::A             A:::::A  
//   GG:::::::::::::::G   CC:::::::::::::::C  A:::::A               A:::::A  
//     GGG::::::GGG:::G     CCC::::::::::::C A:::::A                 A:::::A  
//        GGGGGG   GGGG        CCCCCCCCCCCCCAAAAAAA                   AAAAAAA  
#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
#include <cmath>  
#include <climits>  
#include <vector>  
#include <set>  
#include <map>  
#include <queue>  
#include <cctype>  
#include <utility>  
#include <ctime>  
using namespace std;  
#ifdef DEBUG  
#define debug(...) printf("DEBUG: "),printf(__VA_ARGS__)  
#define gettime() end_time=clock();printf("now running time is %.7f\\n",(float)(end_time - start_time)/CLOCKS_PER_SEC);  
#else  
#define debug(...)  
#define gettime()  
#endif  
typedef unsigned int uint;  
typedef long long int Int;  
#define Set(a,s) memset(a,s,sizeof(a))  
#define Write(w) freopen(w,"w",stdout)  
#define Read(r) freopen(r,"r",stdin)  
#define Pln() printf("\\n")  
#define I_de(x,n)for(int i=0;i<n;i++)printf("%d ",x[i]);Pln()  
#define De(x)printf(#x"%d\\n",x)  
#define For(i,x)for(int i=0;i<x;i++)  
#define CON(x,y) x##y  
#define Pmz(dp,nx,ny)for(int hty=0;hty<ny;hty++){for(int htx=0;htx<nx;htx++){\\  
    printf("%d ",dp[htx][hty]);}Pln();}  
#define M 3005  
#define PII pair<int,int>  
#define PB push_back  
#define oo INT_MAX  
#define Set_oo 0x3f  
#define FOR(it,c) for(vector<PII>::iterator it=(c).begin();it!=(c).end();it++)  
#define eps 1e-6  
clock_t start_time=clock(), end_time;  
bool xdy(double x,double y){return x>y+eps;}  
bool xddy(double x,double y){return x>y-eps;}  
bool xcy(double x,double y){return x<y-eps;}  
bool xcdy(double x,double y){return x<y+eps;}  
int min3(int x,int y,int z){  
    int tmp=min(x,y);  
    return min(tmp,z);  
}  
int max3(int x,int y,int z){  
    int tmp=max(x,y);  
    return max(tmp,z);  
}  
int w,h,n;  
struct pt{  
    int x,y;  
    int w;  
}p[M],p2[M];  
int mz[105][105];  
int mz2[105][105];  
int dx[4]={0,0,1,-1};  
int dy[4]={1,-1,0,0};  
bool cmp(pt a,pt b){  
    return a.w<b.w;  
}  
int main() {  
    ios_base::sync_with_stdio(0);  
    int test;  
    scanf("%d",&test);  
    while(test--){  
        Set(mz,0);  
        Set(mz2,0);  
        scanf("%d%d%d",&w,&h,&n);  
        for(int i=0;i<n;i++){  
            p[i].w=0;  
            scanf("%d%d",&p[i].x,&p[i].y);  
            mz[p[i].x][p[i].y]=1;  
        }  
        for(int i=0;i<n;i++){  
            p2[i].w=0;  
            scanf("%d%d",&p2[i].x,&p2[i].y);  
            mz2[p2[i].x][p2[i].y]=1;  
        }  
        for(int i=0;i<n;i++){  
            int x=p[i].x;  
            int y=p[i].y;  
            int we=1;  
            for(int j=0;j<4;j++){  
                int nex=x+dx[j];  
                int ney=y+dy[j];  
                for(;;){  
//                debug("%d %d %d %d %d %d %d\\n",x,y,nex,ney,mz[nex][ney],w,h);  
                    if(nex<0||nex>=w||ney<0||ney>=h)break;  
//                    debug("ok1\\n");  
                    if(!mz[nex][ney])break;  
//                    debug("ok2\\n");  
                    we++;  
                    nex+=dx[j];ney+=dy[j];  
                }  
            }  
            p[i].w=we;  
            //printf("%d ",p[i].w);  
        }//Pln();  
        for(int i=0;i<n;i++){  
            int x=p2[i].x;  
            int y=p2[i].y;  
            int we=1;  
            for(int j=0;j<4;j++){  
                int nex=x+dx[j];  
                int ney=y+dy[j];  
                for(;;){  
                    if(nex<0||nex>=w||ney<0||ney>=h)break;  
                    if(!mz2[nex][ney])break;  
                    we++;  
                    nex+=dx[j];ney+=dy[j];  
                }  
            }  
            p2[i].w=we;  
            //printf("%d ",p[i].w);  
        }//Pln();  
        sort(p,p+n,cmp);  
        sort(p2,p2+n,cmp);  
        bool ok=true;  
        for(int i=0;i<n;i++){  
            if(p[i].w!=p2[i].w){  
                ok=false;  
                break;  
            }  
        }  
        printf("%s\\n",ok?"YES":"NO");  
    }  
}  

Loading...
Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.