轉載請注明出處：優 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
}
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
