Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

第一次自己写出hash的题目,纪念一下,贴代码。

Posted by hello_hello at 2011-04-19 19:58:29 on Problem 2002
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int SIZE = 40000;
struct node
{
    int x,y;
    node *next;
}nodes[SIZE];
int n;
int map[1005][2];
int find(int x,int y)
{
    int key=(x*x+y*y)%SIZE;
    node *temp=&nodes[key];
    while(temp->next!=NULL)
    {
        temp=temp->next;
        if(temp->x==x && temp->y==y)
          return 1;
    }
    return 0;
}
int main()
{
    while(scanf("%d",&n) && n)
    {
        memset(nodes,0,sizeof(nodes));
        node *point;
        for(int i=1;i<=n;i++)
        {
            point=new node;
            scanf("%d %d",&point->x,&point->y);
            map[i][0]=point->x;
            map[i][1]=point->y;
            point->next=NULL;
            int key=((point->x)*(point->x)+(point->y)*(point->y))%SIZE;
            node *temp=&nodes[key];
            while(temp->next!=NULL)
            {
                temp=temp->next;
            }
            temp->next=point;

        }
        int ans=0;
        for(int i=1;i<=n;i++)
         for(int j=i+1;j<=n;j++)
         {
             int x1=map[i][0]-(map[i][1]-map[j][1]);
             int y1=map[i][1]+(map[i][0]-map[j][0]);
             int x2=map[j][0]-(map[i][1]-map[j][1]);
             int y2=map[j][1]+(map[i][0]-map[j][0]);
             if(find(x1,y1) && find(x2,y2))
                {
                    ans++;
                   // printf("%d %d %d %d\n",x1,y1,x2,y2);
                }
         }

       for(int i=1;i<=n;i++)
         for(int j=i+1;j<=n;j++)
         {
             int x1=map[i][0]+(map[i][1]-map[j][1]);
             int y1=map[i][1]-(map[i][0]-map[j][0]);
             int x2=map[j][0]+(map[i][1]-map[j][1]);
             int y2=map[j][1]-(map[i][0]-map[j][0]);
             if(find(x1,y1) && find(x2,y2))
                {
                    ans++;
                    // printf("%d %d %d %d\n",x1,y1,x2,y2);
                }
         }
        printf("%d\n",ans>>2);
        //printf("%d\n\n\n",ans);
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator