题意:存不存在两片相同的雪花,每片六角形的雪花的每个角的长度给出,可能是顺时针也可能是逆时针给出。最多100 000片雪花。
思路:将六角形的sum%prime之后存起来,雪花相同的前提是sum相同,sum相同再一一比较。
View Code
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 const int N=100005; 8 const int prime=90001; 9 10 int snow[N][6];11 vector hash[prime];12 13 bool judge(int a,int b){14 int i;15 for(i=0;i<6;i++){16 if(/*顺时针方向*/17 (snow[a][0] == snow[b][i] &&18 snow[a][1] == snow[b][(i+1)%6] &&19 snow[a][2] == snow[b][(i+2)%6] &&20 snow[a][3] == snow[b][(i+3)%6] &&21 snow[a][4] == snow[b][(i+4)%6] &&22 snow[a][5] == snow[b][(i+5)%6])23 ||24 /*逆时针方向*/25 (snow[a][0] == snow[b][i] &&26 snow[a][1] == snow[b][(i+5)%6] &&27 snow[a][2] == snow[b][(i+4)%6] &&28 snow[a][3] == snow[b][(i+3)%6] &&29 snow[a][4] == snow[b][(i+2)%6] &&30 snow[a][5] == snow[b][(i+1)%6]) )31 return 1;32 }33 return 0;34 }35 36 int main(){37 int i,j;38 int n;39 scanf("%d",&n);40 int flag=0;41 for(i=0;i