午夜在线成人av,国产精品一区二区久久久,麻豆精品视频在线观看

Pku 1971

2009年7月18日星期六

題目鏈接：PKU 1971 Parallelogram Counting

分類：哈希

題目分析與算法模型：
該題大意是給你平面坐標(biāo)系的n個(gè)點(diǎn)的坐標(biāo)值，然后要你統(tǒng)計(jì)這些點(diǎn)一共可以構(gòu)成多少個(gè)平行四邊形。其實(shí)稍微觀察就能發(fā)現(xiàn)，平行四邊形的特點(diǎn)就是對(duì)角線互相平分，可以利用這一點(diǎn)進(jìn)行Hash，具體做法可以枚舉每兩個(gè)不同的點(diǎn)，然后對(duì)其中點(diǎn)的坐標(biāo)值的和進(jìn)行hash,即若當(dāng)前的一對(duì)點(diǎn)的中點(diǎn)坐標(biāo)的和對(duì)應(yīng)到hash表中有沖突，因?yàn)椴捎玫氖情_鏈表的方式，則一個(gè)一個(gè)比較該中點(diǎn)坐標(biāo)與鏈表中的其他中點(diǎn)的坐標(biāo)是否有重合，若有則表示找到一個(gè)，平行四邊形個(gè)數(shù)加1，然后繼續(xù)向后比較，比到鏈表末尾時(shí)，將該中點(diǎn)元素加入成為新的鏈表末尾

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 閱讀(360) 評(píng)論(0) 編輯收藏引用

只有注冊用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

Pku 1971

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜