题意:
给两个平面,每个平面上有一些点,相邻的点可构成点集,为两个平面内的点集是够都对应相似。两个点集相似是指经过对称或旋转或平移后相等。
分析:
直接模拟判断。
代码:
//poj 1021
//sep9
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int w,h,n;
int g[128][128];
int vis[128][128];
int dirx[4]={0,0,-1,1};
int diry[4]={-1,1,0,0};
struct P
{int x,y;
};
struct AREA
{vector<P> pnts;
}area;
void dfs(int x,int y)
{P p0;p0.x=x,p0.y=y;vis[x][y]=1;area.pnts.push_back(p0);for(int k=0;k<4;++k){int nx=x+dirx[k];int ny=y+diry[k];if(nx>=0&&nx<h&&ny>=0&&ny<w&&vis[nx][ny]==0&&g[nx][ny]==1)dfs(nx,ny);}
}
struct BOARD
{vector<AREA> areas;void ini(){memset(g,0,sizeof(g));memset(vis,0,sizeof(vis));for(int i=0;i<n;++i){int r,c;scanf("%d%d",&c,&r); g[r][c]=1;} for(int i=0;i<h;++i)for(int j=0;j<w;++j){if(vis[i][j]==0&&g[i][j]==1){area.pnts.clear();dfs(i,j);areas.push_back(area);} } }
};
BOARD a,b;bool cmp(P u,P v)
{if(u.x!=v.x)return u.x<v.x;return u.y<v.y;
}bool judge(AREA p,AREA q)
{sort(p.pnts.begin(),p.pnts.end(),cmp);sort(q.pnts.begin(),q.pnts.end(),cmp);int dx=q.pnts[0].x-p.pnts[0].x;int dy=q.pnts[0].y-p.pnts[0].y;for(int i=p.pnts.size()-1;i>=0;--i)if(p.pnts[i].x+dx!=q.pnts[i].x||p.pnts[i].y+dy!=q.pnts[i].y)return false;return true;
}bool compare(AREA p,AREA q)
{AREA tmp;P tmp_p;for(int i=0;i<q.pnts.size();++i)tmp.pnts.push_back(q.pnts[i]);if(judge(p,tmp))return true;tmp.pnts.clear();for(int i=0;i<q.pnts.size();++i){tmp_p.x=-q.pnts[i].x;tmp_p.y=-q.pnts[i].y;tmp.pnts.push_back(tmp_p);}if(judge(p,tmp))return true;tmp.pnts.clear();for(int i=0;i<q.pnts.size();++i){tmp_p.x=q.pnts[i].x;tmp_p.y=-q.pnts[i].y;tmp.pnts.push_back(tmp_p);}if(judge(p,tmp))return true;tmp.pnts.clear();for(int i=0;i<q.pnts.size();++i){tmp_p.x=-q.pnts[i].x;tmp_p.y=q.pnts[i].y;tmp.pnts.push_back(tmp_p);}if(judge(p,tmp))return true;tmp.pnts.clear();for(int i=0;i<q.pnts.size();++i){tmp_p.x=q.pnts[i].y;tmp_p.y=q.pnts[i].x;tmp.pnts.push_back(tmp_p);}if(judge(p,tmp))return true; tmp.pnts.clear();for(int i=0;i<q.pnts.size();++i){tmp_p.x=-q.pnts[i].y;tmp_p.y=-q.pnts[i].x;tmp.pnts.push_back(tmp_p);}if(judge(p,tmp))return true;tmp.pnts.clear();for(int i=0;i<q.pnts.size();++i){tmp_p.x=q.pnts[i].y;tmp_p.y=-q.pnts[i].x;tmp.pnts.push_back(tmp_p);}if(judge(p,tmp))return true;tmp.pnts.clear();for(int i=0;i<q.pnts.size();++i){tmp_p.x=-q.pnts[i].y;tmp_p.y=q.pnts[i].x;tmp.pnts.push_back(tmp_p);}if(judge(p,tmp))return true;return false;
}bool find(AREA s,BOARD T)
{for(int i=0;i<T.areas.size();++i){if(s.pnts.size()!=T.areas[i].pnts.size())continue;if(compare(s,T.areas[i]))return true;}return false;
}bool match()
{if(a.areas.size()!=b.areas.size())return false;for(int i=0;i<a.areas.size();++i)if(!find(a.areas[i],b))return false;for(int i=0;i<b.areas.size();++i)if(!find(b.areas[i],a))return false;return true;
}
int main()
{int cases;scanf("%d",&cases);while(cases--){scanf("%d%d%d",&w,&h,&n);a.areas.clear();b.areas.clear();a.ini();b.ini();if(match())puts("YES");elseputs("NO");}
}