如果用過Hash,那么可能主要是算坐標(biāo)的問題
1 #include <cstdio>
2 #include <cmath>
3 #include <algorithm>
4 using namespace std ;
5
6 const int MAXN = 1101 ;
7 const int KEY = 20011 ;
8 const int MUL = 33 ;
9
10 struct NODE
11 {
12 int x , y ;
13 NODE *next ;
14
15 NODE(){ next = NULL; }
16 }hash[KEY] , gTemp[MAXN];
17
18 int gPos ;
19
20 struct POINT
21 {
22 int x, y ;
23
24 }g_star[MAXN] ;
25
26 int N ;
27
28 bool cmp( const POINT& a, const POINT& b )
29 {
30 if ( a.x < b.x ){
31 return true ;
32 }
33 else if ( a.x == b.x )
34 {
35 if ( a.y > b.y )
36 {
37 return true ;
38 }
39 else
40 return false ;
41 }
42 return false ;
43 }
44 //計(jì)算哈希值
45 int Cal( const int& sx, const int& sy )
46 {
47 int val , x = abs(sx), y = abs(sy) ;
48
49 val = (x * MUL + y) % KEY ;
50
51 return val ;
52 }
53
54 bool Find( const int& x, const int& y )
55 {
56 int pos = Cal( x, y ) ;
57
58 NODE *ptr = hash[pos].next ;
59
60 while ( ptr )
61 {
62 if ( ptr->x == x && ptr->y == y )
63 {
64 return true ;
65 }
66 ptr = ptr->next ;
67 }
68
69 return false ;
70 }
71
72 void Insert( const int& x, const int& y )
73 {
74 int pos = Cal( x, y ) ;
75
76 NODE *ptr = &gTemp[gPos++] ;
77
78 ptr->x = x ;
79 ptr->y = y ;
80 ptr->next = hash[pos].next ;
81 hash[pos].next = ptr ;
82 }
83 //判斷是否能組成一個(gè)正方形而且不重復(fù)
84 bool Judge( const POINT& a, const POINT& b )
85 {
86 int dx = ( b.x - a.x ) , dy = ( b.y - a.y ) ;
87 int x1, y1, x2, y2 ;
88 int flag = dx * dy ;
89
90 dx = abs(dx) ;
91 dy = abs(dy) ;
92
93 if ( flag > 0 )
94 {
95 x1 = a.x - dy , y1 = a.y + dx ;
96 x2 = b.x - dy , y2 = b.y + dx ;
97 }
98 else {
99 x1 = a.x + dy , y1 = a.y + dx ;
100 x2 = b.x + dy , y2 = b.y + dx ;
101 }
102
103 if ( x1 <= a.x )
104 return false ;
105
106 if ( Find( x1, y1 ) && Find( x2, y2 ) )
107 return true ;
108
109 return false ;
110 }
111
112 void Init()
113 {
114 gPos = 0 ;
115 for ( int i = 0 ; i < KEY ; ++i )
116 {
117 hash[i].next = NULL ;
118 }
119 }
120
121 int main()
122 {
123 //freopen("in", "r", stdin) ;
124
125 int i , j , count ;
126
127 while ( scanf("%d", &N) && N != 0 )
128 {
129 Init() ;
130 count = 0 ;
131
132 for ( i = 0 ; i < N ; ++i )
133 {
134 scanf("%d %d", &g_star[i].x, &g_star[i].y) ;
135 Insert( g_star[i].x, g_star[i].y ) ;
136 }
137 //按左到右，上到下
138 sort(g_star, g_star + N, cmp) ;
139
140 for ( i = 0 ; i < N - 1 ; ++i )
141 {
142 for ( j = i + 1 ; j < N ; ++j )
143 {
144 if ( Judge(g_star[i], g_star[j]) )
145 count++ ;
146
147 }
148 }
149
150 printf("%d\n", count) ;
151 }
152
153 return 0 ;
154 }
155