poj Squares n个点，共能组成多少个正方形二分 + 哈希

题目链接：http://poj.org/problem?id=2002

测试数据：

4
1 0
0 1
1 1
0 0
9
0 0
1 0
2 0
0 2
1 2
2 2
0 1
1 1
2 1
4
-2 5
3 7
0 0
5 2
0

有两种解法，第一种用二分查找，第二种用到hash存储：

解法一：

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 int T;
 8 struct TT
 9 {
10     int x,y;
11 }node[1010];
12 bool cmp(TT a,TT b)
13 {
14     if(a.x<b.x ||(a.x==b.x && a.y<b.y))  return true;
15     return false;
16 }
17 bool judge(int x,int y)
18 {
19     int L = 1,R =T;
20    while(L<=R)
21     {
22        int mid = (L+R)/2;
23        if(node[mid].x == x && node[mid].y == y)
24        {
25            return true;
26        }
27        if(x == node[mid].x )   //这个地方老是出错，就是当x值相同的时候，会有两种情况的，我只是考虑了一种
28        {
29            if(y>node[mid].y) L = mid +1;
30                else  R = mid-1;
31        }
32        else if(x>node[mid].x) L = mid+1;
33          else                R = mid-1;
34     }
35     return false;
36 }
37 int main()
38 {
39    int ans;
40    int x1,y1,x2,y2,mx,my;
41    while(scanf("%d",&T) && T)
42    { ans = 0;
43        for(int i =1;i<=T;i++)
44           scanf("%d %d",&node[i].x,&node[i].y);
45           sort(node+1,node+T+1,cmp);//乱了一下，开始从0，开始排序了
46           for(int i  = 1; i<T; i++)
47             for(int j = i+1; j<=T; j++)
48             {
49               mx = node[j].x - node[i].x;
50               my = node[j].y - node[i].y;
51               x1 = node[i].x+my;
52               y1 = node[i].y-mx;
53               x2 = node[j].x+my;
54               y2 = node[j].y-mx;
55               if( judge(x1,y1) &&  judge(x2,y2))
56               {
57                     ans++;
58               }
59             }
60             printf("%d
",ans/2);//因为每次都有两个重复；
61    }
62     return 0;
63 }

解法二：本来想着哈希简简单单就过了呢，咋说也比二分省时间吧，可是呢，整了两个小时才搞定，还发现了一个问题；有待于求证：结构体数组赋值时间小于数组赋值时间，

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 struct TT
 8 {
 9     int x,y,next;
10 }node[1010],hash[1010];
11 const int N = 1100;
12 int vis[N][N];
13 int T;
14 const int MOD  = 10007;
15 int next[N],head[MOD],top = 1;
16 void creath(int x,int y)
17 {
18     int key = abs(x)%MOD;
19     hash[top].next  = head[key];//这样写超时：  next[top] = head[key];
20     hash[top].x = x;
21     hash[top].y = y;
22     head[key] = top;
23     top++;
24 }
25 bool cmp(TT a,TT b)
26 {
27     if(a.x<b.x || (a.x == b.x && a.y<b.y))  return true;
28     return false;
29 }
30 bool judge(int x,int y)
31 {
32       int key = abs(x)%MOD;
33       int ans = 0;
34       for(int i = head[key];i>=0;i = hash[i].next)//换成 i = next[i]  超时
35       {
36         if(hash[i].x==x && hash[i].y == y)
37            return true;
38       }
39         return false;
40 }
41 int main()
42 {
43    int ans;
44    int x1,y1,x2,y2,mx,my;
45    while(scanf("%d",&T) && T)
46    {   memset(head,-1,sizeof(head));
47        ans = 0;
48        for(int i =1;i<=T;i++)
49        {
50           scanf("%d %d",&node[i].x,&node[i].y);
51           creath(node[i].x,node[i].y);
52        }
53           sort(node+1,node+1+T,cmp);
54           for(int i  = 1; i<T; i++)
55             for(int j = i+1; j<=T; j++)
56             {
57               mx = node[j].x - node[i].x;
58               my = node[j].y - node[i].y;
59               x1 = node[i].x+my;
60               y1 = node[i].y-mx;
61               x2 = node[j].x+my;
62               y2 = node[j].y-mx;
63               if( judge(x1,y1) &&  judge(x2,y2))
64               {
65                     ans++;
66               }
67             }
68             printf("%d
",ans/2);
69    }
70     return 0;
71 }

poj Squares n个点，共能组成多少个正方形 二分 + 哈希

poj Squares n个点，共能组成多少个正方形二分 + 哈希