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
 7int t,n,i,j,start,sum,count,pos[max][2];
 8struct node
 9{
10    int midx,midy,next;
11}hash[len];
12bool 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}
17void 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}
29int 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 阅读(331) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年7月>
日一二三四五六
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜