国产亚洲精品激情久久,欧美日韩精品免费,欧美成黄导航

對于蝸牛來說，狂奔雖不代表極速，但展現的卻是一種拼盡全力的姿態........

Pku 1971

2009年7月18日星期六

題目鏈接：PKU 1971 Parallelogram Counting

分類：哈希

題目分析與算法模型：
該題大意是給你平面坐標系的n個點的坐標值，然后要你統計這些點一共可以構成多少個平行四邊形。其實稍微觀察就能發現，平行四邊形的特點就是對角線互相平分，可以利用這一點進行Hash，具體做法可以枚舉每兩個不同的點，然后對其中點的坐標值的和進行hash,即若當前的一對點的中點坐標的和對應到hash表中有沖突，因為采用的是開鏈表的方式，則一個一個比較該中點坐標與鏈表中的其他中點的坐標是否有重合，若有則表示找到一個，平行四邊形個數加1，然后繼續向后比較，比到鏈表末尾時，將該中點元素加入成為新的鏈表末尾

Code:

1

#include<stdio.h>
2

#include<math.h>
3

#include<string.h>
4

#define max 1005
5

#define prime 499997
6

#define len 1100000
7

int t,n,i,j,start,sum,count,pos[max][2];
8

struct node
9

{
10

int midx,midy,next;
11

}hash[len];
12

bool check(int a,int b)
13

{
14

if(hash[a].midx==hash[b].midx&&hash[a].midy==hash[b].midy)return true;
15

else return false;
16

}
17

void Hash(int k)
18

{
19

int now=k%prime;
20

while(hash[now].next!=-1)
21

{
22

if(check(start,hash[now].next))count++;
23

now=hash[now].next;
24

}
25

hash[start].next=-1;
26

hash[now].next=start;
27

start++;
28

}
29

int main()
30

{
31

scanf("%d",&t);
32

while(t--)
33

{
34

scanf("%d",&n);
35

for(i=0;i<n;i++)scanf("%d%d",&pos[i][0],&pos[i][1]);
36

start=prime+10;
37

memset(hash,-1,sizeof(hash));
38

count=0;
39

for(i=0;i<n-1;i++)
40

for(j=i+1;j<n;j++)
41

{
42

hash[start].midx=pos[i][0]+pos[j][0];
43

hash[start].midy=pos[i][1]+pos[j][1];
44

sum=hash[start].midx+hash[start].midy;
45

if(sum<0)sum*=-1;
46

Hash(sum);
47

}
48

printf("%d\n",count);
49

}
50

return 0;
51

}
52

53

54

posted on 2009-07-18 23:31 蝸牛也Coding 閱讀(365) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

<

2015年9月

>

日

一

二

三

四

五

六

30

31

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

1

2

3

4

5

6

7

8

9

10

統計

隨筆 - 78
文章 - 0
評論 - 96
引用 - 0

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

積分 - 95328
排名 - 261

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

Pku 1971

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜