转载请注明出处：優 YoU http://user.qzone.qq.com/289065406/blog/1304781008
POJ2002 的山寨题，把数据规模从 2002 的 n=1000 修改为 n=2000 就能 AC 了
注意这种题一定不能图方便用 STL 的 map 标记， map 效率不高，必定超时的 .
解题思路参看POJ2002：
http://blog.csdn.net/lyy289065406/article/details/6647405
1
//
Memory Time
2
//
336K 313MS
3
4
#include
<
iostream
>
5
using
namespace
std;
6
7
const
int
prime
=
1999
;
//
长度为n区间的最大素数 (本题n=2000)
8
9
typedef
class
10
{
11
public
:
12
int
x,y;
13
}Node;
14
15
typedef
class
HashTable
16
{
17
public
:
18
int
x,y;
//
标记key值对应的x,y
19
HashTable
*
next;
//
当出现地址冲突时，开放寻址
20
21
HashTable()
//
Initial
22
{
23
next
=
0
;
24
}
25
}Hashtable;
26
27
Node pos[
2001
];
28
Hashtable
*
hash[prime];
//
hash[]是指针数组，存放地址
29
30
void
insert_vist(
int
k)
31
{
32
int
key
=
((pos[k].x
*
pos[k].x)
+
(pos[k].y
*
pos[k].y))
%
prime
+
1
;
//
+1是避免==0
33
//
使key从[0~1998]后移到[1~1999]
34
if
(
!
hash[key])
35
{
36
Hashtable
*
temp
=
new
Hashtable;
37
temp
->
x
=
pos[k].x;
38
temp
->
y
=
pos[k].y;
39
hash[key]
=
temp;
40
}
41
else
//
hash[key]已存地址，地址冲突
42
{
43
Hashtable
*
temp
=
hash[key];
44
45
while
(temp
->
next)
//
开放寻址，直至next为空
46
temp
=
temp
->
next;
47
48
temp
->
next
=
new
HashTable;
//
申请新结点，用next指向，记录x、y
49
temp
->
next
->
x
=
pos[k].x;
50
temp
->
next
->
y
=
pos[k].y;
51
}
52
return
;
53
}
54
55
bool
find(
int
x,
int
y)
56
{
57
int
key
=
((x
*
x)
+
(y
*
y))
%
prime
+
1
;
58
59
if
(
!
hash[key])
//
key对应的地址不存在
60
return
false
;
61
else
62
{
63
Hashtable
*
temp
=
hash[key];
64
65
while
(temp)
66
{
67
if
(temp
->
x
==
x
&&
temp
->
y
==
y)
68
return
true
;
69
70
temp
=
temp
->
next;
71
}
72
}
73
74
return
false
;
75
}
76
77
int
main(
void
)
78
{
79
int
n;
80
while
(cin
>>
n)
81
{
82
if
(
!
n)
83
break
;
84
85
memset(hash,
0
,
sizeof
(hash));
//
0 <-> NULL
86
87
for
(
int
k
=
1
;k
<=
n;k
++
)
88
{
89
cin
>>
pos[k].x
>>
pos[k].y;
90
insert_vist(k);
//
插入哈希表，标记散点
91
}
92
93
int
num
=
0
;
//
正方形的个数
94
for
(
int
i
=
1
;i
<=
n
-
1
;i
++
)
95
for
(
int
j
=
i
+
1
;j
<=
n;j
++
)
96
{
97
int
a
=
pos[j].x
-
pos[i].x;
98
int
b
=
pos[j].y
-
pos[i].y;
99
100
int
x3
=
pos[i].x
+
b;
101
int
y3
=
pos[i].y
-
a;
102
int
x4
=
pos[j].x
+
b;
103
int
y4
=
pos[j].y
-
a;
104
105
if
(find(x3,y3)
&&
find(x4,y4))
106
num
++
;
107
108
x3
=
pos[i].x
-
b;
109
y3
=
pos[i].y
+
a;
110
x4
=
pos[j].x
-
b;
111
y4
=
pos[j].y
+
a;
112
113
if
(find(x3,y3)
&&
find(x4,y4))
114
num
++
;
115
}
116
117
cout
<<
num
/
4
<<
endl;
//
同一个正方形枚举了4次
118
}
119
return
0
;
120
}
