poj Squares n个点，共能组成多少个正方形二分 + 哈希

题目链接：http://poj.org/problem?id=2002

测试数据：

4
1 0
0 1
1 1
0 0
9
0 0
1 0
2 0
0 2
1 2
2 2
0 1
1 1
2 1
4
-2 5
3 7
0 0
5 2
0

有两种解法，第一种用二分查找，第二种用到hash存储：

解法一：

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 using namespace std;

 int T;

 struct TT

 {

     int x,y;

 }node[];

 bool cmp(TT a,TT b)

 {

     if(a.x<b.x ||(a.x==b.x && a.y<b.y))  return true;

     return false;

 }

 bool judge(int x,int y)

 {

     int L = ,R =T;

    while(L<=R)

     {

        int mid = (L+R)/;

        if(node[mid].x == x && node[mid].y == y)

        {

            return true;

        }

        if(x == node[mid].x )   //这个地方老是出错，就是当x值相同的时候，会有两种情况的，我只是考虑了一种

        {

            if(y>node[mid].y) L = mid +;

                else  R = mid-;

        }

        else if(x>node[mid].x) L = mid+;

          else                R = mid-;

     }

     return false;

 }

 int main()

 {

    int ans;

    int x1,y1,x2,y2,mx,my;

    while(scanf("%d",&T) && T)

    { ans = ;

        for(int i =;i<=T;i++)

           scanf("%d %d",&node[i].x,&node[i].y);

           sort(node+,node+T+,cmp);//乱了一下，开始从0，开始排序了

           for(int i  = ; i<T; i++)

             for(int j = i+; j<=T; j++)

             {

               mx = node[j].x - node[i].x;

               my = node[j].y - node[i].y;

               x1 = node[i].x+my;

               y1 = node[i].y-mx;

               x2 = node[j].x+my;

               y2 = node[j].y-mx;

               if( judge(x1,y1) &&  judge(x2,y2))

               {

                     ans++;

               }

             }

             printf("%d\n",ans/);//因为每次都有两个重复；

    }

     return ;

 }

解法二：本来想着哈希简简单单就过了呢，咋说也比二分省时间吧，可是呢，整了两个小时才搞定，还发现了一个问题；有待于求证：结构体数组赋值时间小于数组赋值时间，

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 using namespace std;

 struct TT

 {

     int x,y,next;

 }node[],hash[];

 const int N = ;

 int vis[N][N];

 int T;

 const int MOD  = ;

 int next[N],head[MOD],top = ;

 void creath(int x,int y)

 {

     int key = abs(x)%MOD;

     hash[top].next  = head[key];//这样写超时：  next[top] = head[key];

     hash[top].x = x;

     hash[top].y = y;

     head[key] = top;

     top++;

 }

 bool cmp(TT a,TT b)

 {

     if(a.x<b.x || (a.x == b.x && a.y<b.y))  return true;

     return false;

 }

 bool judge(int x,int y)

 {

       int key = abs(x)%MOD;

       int ans = ;

       for(int i = head[key];i>=;i = hash[i].next)//换成 i = next[i]  超时

       {

         if(hash[i].x==x && hash[i].y == y)

            return true;

       }

         return false;

 }

 int main()

 {

    int ans;

    int x1,y1,x2,y2,mx,my;

    while(scanf("%d",&T) && T)

    {   memset(head,-,sizeof(head));

        ans = ;

        for(int i =;i<=T;i++)

        {

           scanf("%d %d",&node[i].x,&node[i].y);

           creath(node[i].x,node[i].y);

        }

           sort(node+,node++T,cmp);

           for(int i  = ; i<T; i++)

             for(int j = i+; j<=T; j++)

             {

               mx = node[j].x - node[i].x;

               my = node[j].y - node[i].y;

               x1 = node[i].x+my;

               y1 = node[i].y-mx;

               x2 = node[j].x+my;

               y2 = node[j].y-mx;

               if( judge(x1,y1) &&  judge(x2,y2))

               {

                     ans++;

               }

             }

             printf("%d\n",ans/);

    }

     return ;

 }

巴特西

poj Squares n个点，共能组成多少个正方形二分 + 哈希

最新文章

热门文章

巴特西

poj Squares n个点，共能组成多少个正方形 二分 + 哈希

最新文章

热门文章

poj Squares n个点，共能组成多少个正方形二分 + 哈希