poj 2002 Squares(查找)

Memory: 8416K

Time: 1797MS

解题思路

题意：

   给出一些点的坐标，算出这些点能组成多少个正方形。

 

思路：

   枚举所有的两个点的组合，以这两个点为边，计算出要组成正方形的话另两个点的坐标，

    公式没有推出来，参考了网上的：如果A(x1, y1), B(x2, y2) ,则C(x3, y3),D(x4, y4) 为：

       x3=x1+(y1-y2);y3=y1-(x1-x2);   (在直线AB上方)

x4=x2+(y1-y2);y4=y2-(x1-x2)

或：   x3=x1-(y1-y2);y3=y1+(x1-x2);   (在直线AB下方)

x4=x2-(y1-y2);y4=y2+(x1-x2)

 

查找顶点要用到hash，hash函数是 d = (x*x + y*y) % N;  （N是hash表长度，也就是顶点个数）。用链表解决冲突。查找时需要判断顶点的x值跟y值是否都相同。枚举边的时候查找，每条边要上下都找一次，防止找漏了。所以每个正方形计算了四次，所以输出时需要除以4。

源程序

 

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#define N 1002
#define M N*(N-1)/2

typedef struct
{
    int x;
    int y;
}node;
node nodes[N];

typedef struct
{
    node n1;
    node n2;
}dia;
dia dias[M];

struct enode
{
    node n;
    struct enode *next;
}elemnode;
struct no
{
    struct enode *first;
} hashtable[N];

int r = 1;
void insert(int x, int y)
{
    struct enode *p;
    int key;

    key = (x*x + y*y) % N;
    p = (struct enode *)malloc(sizeof(struct enode));
    p->n.x = x;
    p->n.y = y;
    p->next = hashtable[key].first;
    hashtable[key].first = p;
}
struct enode *find(node n)
{
    struct enode *p;
    int key;

    key = (n.x*n.x+n.y*n.y) % N;
    p = hashtable[key].first;
    while(p!=NULL)
    {
        if(p->n.y == n.y && p->n.x == n.x)
            break;
        p = p->next;
    }
    return p;
}

int main()
{
    int i, j, k;
    int n, count, dx, dy;

    freopen("in.txt", "r", stdin);
    while(scanf("%d", &n) && n)
    {    
        memset(hashtable, 0, sizeof(hashtable));
        i=0;
        memset(nodes, 0, sizeof(nodes));
        while(i < n)
        {
            scanf("%d%d", &nodes[i].x, &nodes[i].y);
            insert(nodes[i].x, nodes[i].y);
            i++;
        }
        memset(dias, 0, sizeof(dias));
        count = 0;
        for(i=0, k=0; i<n; i++)
            for(j=i+1; j<n; j++)
            {
                dx = nodes[i].x - nodes[j].x;
                dy = nodes[i].y - nodes[j].y;

                dias[k].n1.x = nodes[i].x - dy;
                dias[k].n1.y = nodes[i].y + dx;
                dias[k].n2.x= nodes[j].x - dy;
                dias[k].n2.y = nodes[j].y + dx;
                if(find(dias[k].n1)!=NULL && find(dias[k].n2)!=NULL)
                    count++;

                dias[k].n1.x = nodes[i].x + dy;
                dias[k].n1.y = nodes[i].y - dx;
                dias[k].n2.x= nodes[j].x + dy;
                dias[k].n2.y = nodes[j].y - dx;
                if(find(dias[k].n1)!=NULL && find(dias[k].n2)!=NULL)
                    count++;

                k++;
            }
        printf("%d\n", count/4);
    }
    getch();
    return 0;
}