久久精品国产黑森林,久久不射电影网,久久久久99这里有精品10

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

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

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



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

Pku 1971

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜