首页 > 代码库 > Hash poj2002 Squares

Hash poj2002 Squares

2024-07-06 12:26:44   224人阅读

仿照之前的雪花，Hash函数随便搞个。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <string>
#include <iostream>
const int INF = 9973;
const int kk = 1007;
struct Node
{
    int x;int y; int hash_val;
}node[INF][100];
int Abs(int x)
{
    return x>0?x:-x;
}
int get_hash(Node &a)
{
    a.hash_val= a.x*a.y+a.y*kk;
    return a.hash_val = Abs(a.hash_val)%INF;
}
int Hash(int x,int y)
{
    return Abs(x*y+y*kk)%INF;
}
int len[INF];
void Insert(Node a)
{
    int val=get_hash(a);
    for(int i=0;i<len[a.hash_val];i++)
        if(node[val][i].x==a.x&&node[val][i].y==a.y)
        return ;
    node[val][len[a.hash_val]++]=a;
}
int match(int  x,int y)
{
    int hash1=Hash(x,y);
    for(int i=0;i<len[hash1];i++)
        if(node[hash1][i].x==x&&node[hash1][i].y==y)
        return 1;
    return 0;
}
int main()
{
    int n;
    Node a[20000];
    while(scanf("%d",&n),n){
        memset(node,0,sizeof(node));
        memset(len,0,sizeof(len));
        for(int i=0;i<n;i++){
            scanf("%d%d",&a[i].x,&a[i].y);
            int val=get_hash(a[i]);
            Insert(a[i]);
        }
        int ans=0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                int x1=a[i].x-a[i].y+a[j].y;int y1=a[i].y-a[j].x+a[i].x;
                int x2=a[j].x+a[j].y-a[i].y;int y2=a[j].y-a[j].x+a[i].x;
                int x3=a[i].x-a[j].y+a[i].y;int y3=a[i].y-a[i].x+a[j].x;
                int x4=a[j].x-a[j].y+a[i].y;int y4=a[j].y+a[j].x-a[i].x;
                if(match(x1,y1)&&match(x2,y2))
                    ans++;
                if(match(x3,y3)&&match(x4,y4))
                    ans++;
            }
        }
        printf("%d\n",ans/4);
    }
    return 0;
}

　　


联系
我们