pku 2002

2009年7月18日 星期六

题目链接：PKU 2002 Squares

分类：哈希

题目分析与算法原型
         其实该题和1971很像（还有3432题除了输入的点的范围其他的基本和这题一模一样）区别在于这题是统计正方形个数，而那题是统计平行四边形个数，个人感觉这题稍微复杂一些，因为正方形属于平行四边形，我用那题的思路，将那题的代码改了一下，即在平行四边形的基础上判断是否是正方形，结果TLE了，只能另找方法了。

 算法1：其实可以发现一点，就是如果给你一个正方形的两个对角线点的坐标，则根据正方形的特点，一定可以算出另外的两点的坐标，利用这一点，这道题目基本就可以hash了，具体做法是，先将读入的n个点的坐标按照其x坐标作为关键值进行hash,然后像1971一样枚举每两个不同的点，将他们作为某个正方形的对角线，算出两外的两个点，然后对于新算出的两个点的x坐标进行hash查找，对于x相同的点，判断y是否也相同，若相同，则继续hash另一个点的坐标，若两次都能找到则正方形个数加1。在哈希判断时若找到相同的则直接退出本次查找，否则一直查找到链表的末尾，表示没有以该两点作为对角线的正方形。
       
算法2：这道题目还可以不用哈希，直接用二分来查找，同算法一，也是先枚举每两个点，根据公式算出另外的两个点，不过，直接用二分来查找这两个点是否存在，当然了，事先需要对输入的坐标排个序，先按x坐标从小到大排序，相同的x的点以y坐标从小到大排序，二分检测时候，先找到与当前被检索的点的x坐标相同的所有点的下标范围，然后再次在这个范围里面再次二分查找是否存在与其y坐标相同的点.........
        需要注意的是这种方法，对于同一个正方形来说，因为与两条对角线，所以会算了两次，所以最后输出的时候需要除以2，呵呵

Code1:

 1#include<stdio.h>
 2#include<math.h>
 3#include<string.h>
 4#define max 1005
 5#define pianyi 20005
 6#define prime 39997
 7#define len 50000
 8int n,i,j,start,sum,count,pos[max][2];
 9double x[3],y[3];
10
11struct node
12{
13    int px,py;
14    int next;
15}hash[len];
16
17void cal(int a,int b)
18{
19    double x0=(double)(pos[a][0]+pos[b][0])/2,y0=(double)(pos[a][1]+pos[b][1])/2;
20    if((pos[b][1]-pos[a][1])*(pos[b][0]-pos[a][0])>0)
21    {
22        x[1]=x0-fabs(pos[b][1]-pos[a][1])/2;
23        x[2]=x0+fabs(pos[b][1]-pos[a][1])/2;
24        y[1]=y0+fabs(pos[b][0]-pos[a][0])/2;
25        y[2]=y0-fabs(pos[b][0]-pos[a][0])/2;
26    }
27    else
28    {
29        x[1]=x0-fabs(pos[b][1]-pos[a][1])/2;
30        x[2]=x0+fabs(pos[b][1]-pos[a][1])/2;
31        y[1]=y0-fabs(pos[b][0]-pos[a][0])/2;
32        y[2]=y0+fabs(pos[b][0]-pos[a][0])/2;
33    }
34}
35int Hash2(int x,int y)
36{
37    int now=x%prime;
38    while(hash[now].next!=-1)
39    {
40        if(hash[hash[now].next].py==y)return 1;
41        now=hash[now].next;
42    }
43    return 0;
44}
45void Hash(int k)
46{
47    int now=k%prime;
48    while(hash[now].next!=-1)now=hash[now].next;
49    hash[start].next=-1;
50    hash[now].next=start;
51    start++;
52}
53int main()
54{
55    while(scanf("%d",&n)!=EOF&&n)
56    {
57        start=prime+10;
58        memset(hash,-1,sizeof(hash));
59        for(i=0;i<n;i++)
60        {
61            scanf("%d%d",&pos[i][0],&pos[i][1]);
62            hash[start].px=pos[i][0];
63            hash[start].py=pos[i][1];
64            Hash(pos[i][0]+pianyi);
65        }
66        count=0;    
67        for(i=0;i<n-1;i++)
68            for(j=i+1;j<n;j++)
69            {
70                int res1,res2;
71                cal(i,j);
72                int t1=(int)x[1],t2=(int)x[2],t3=(int)y[1],t4=(int)y[2];
73                if(t1!=x[1]||t2!=x[2]||t3!=y[1]||t4!=y[2])continue;
74                res1=Hash2((int)x[1]+pianyi,(int)y[1]);
75                res2=Hash2((int)x[2]+pianyi,(int)y[2]);
76                if(res1&&res2)count++;
77            }
78            printf("%d\n",count/2);
79    }
80    return 0;
81}
82
83
  Code2:

  1#include<stdio.h>
  2#include<stdlib.h>
  3#include<math.h>
  4#include<string.h>
  5#define max 2005
  6
  7int n,i,j,start,sum,count;
  8double x[3],y[3];
  9
 10struct node
 11{
 12    int px,py;
 13}pos[max];
 14
 15int cmp(const void *a,const void *b)
 16{
 17    struct node *c=(node *)a;
 18    struct node *d=(node *)b;
 19    if(c->px!=d->px)return c->px-d->px;
 20    else return c->py-d->py;
 21}
 22
 23int search2(int low,int high,int y)
 24{
 25    int mid;
 26    while(low<=high&&low>=0&&high<n)
 27    {
 28        mid=(low+high)/2;
 29        if(y<pos[mid].py)high=mid-1;
 30        else if(y>pos[mid].py)low=mid+1;
 31        else return 1;
 32    }
 33    return 0;
 34}
 35
 36int search(int low,int high,int x,int y)
 37{
 38    int mid;
 39    while(low<=high&&low>=0&&high<n)
 40    {
 41        mid=(low+high)/2;
 42        if(x<pos[mid].px)high=mid-1;
 43        else if(x>pos[mid].px)low=mid+1;
 44        else
 45        {
 46            int start=mid,end=mid;
 47            while(pos[start].px==x&&start>=0)start--;
 48            while(pos[end].px==x&&end<n)end++;
 49            return search2(start+1,end-1,y);
 50        }
 51    }
 52    return 0;
 53}
 54
 55
 56
 57void cal(int a,int b)
 58{
 59    double x0=(double)(pos[a].px+pos[b].px)/2,y0=(double)(pos[a].py+pos[b].py)/2;
 60    if((pos[b].py-pos[a].py)*(pos[b].px-pos[a].px)>0)
 61    {
 62        x[1]=x0-fabs(pos[b].py-pos[a].py)/2;
 63        x[2]=x0+fabs(pos[b].py-pos[a].py)/2;
 64        y[1]=y0+fabs(pos[b].px-pos[a].px)/2;
 65        y[2]=y0-fabs(pos[b].px-pos[a].px)/2;
 66    }
 67    else
 68    {
 69        x[1]=x0-fabs(pos[b].py-pos[a].py)/2;
 70        x[2]=x0+fabs(pos[b].py-pos[a].py)/2;
 71        y[1]=y0-fabs(pos[b].px-pos[a].px)/2;
 72        y[2]=y0+fabs(pos[b].px-pos[a].px)/2;
 73    }
 74}
 75
 76int main()
 77{
 78    while(scanf("%d",&n)!=EOF&&n)
 79    {
 80        for(i=0;i<n;i++)scanf("%d%d",&pos[i].px,&pos[i].py);
 81        qsort(pos,n,sizeof(pos[0]),cmp);    
 82        count=0;    
 83        for(i=0;i<n-1;i++)
 84            for(j=i+1;j<n;j++)
 85            {
 86                int res1,res2;
 87                cal(i,j);
 88                int t1=(int)x[1],t2=(int)x[2],t3=(int)y[1],t4=(int)y[2];
 89                if(t1!=x[1]||t2!=x[2]||t3!=y[1]||t4!=y[2])continue;
 90                res1=search(0,n-1,x[1],y[1]);
 91                if(!res1)continue;
 92                res2=search(0,n-1,x[2],y[2]);
 93                if(res1&&res2)count++;
 94            }
 95            printf("%d\n",count/2);
 96    }
 97    return 0;
 98}
 99
100

posted on 2009-07-18 23:45 蜗牛也Coding 阅读(632) 评论(1)  编辑 收藏 引用

评论

# re: pku 2002 2009-08-20 20:48 ning

2分法的那个bsearch函数不能用么？  回复  更多评论   


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


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

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜