poj2002

题意：给出一些平面上点的坐标，用其中的点做顶点，求其中能组成正方形的个数。

分析：每次枚举两个点，用hash看另外两个点存不存在。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
usingnamespace std;

#define maxn 1005

struct XPoint
{
    int x, y;
} point[maxn];

struct Hash
{
    XPoint p;
    Hash *next;
} h[maxn];

int n, ans;

int hash(XPoint &a)
{
    return ((a.x + a.y) % maxn + maxn) % maxn;
}

void ins(XPoint &a)
{
    Hash *temp =new Hash();
    int index = hash(a);
    temp->p.x = a.x;
    temp->p.y = a.y;
    temp->next = h[index].next;
    h[index].next = temp;
}

void input()
{
    for (int i =0; i < n; i++)
    {
        scanf("%d%d", &point[i].x, &point[i].y);
        ins(point[i]);
    }
}

bool exist(XPoint &a)
{
    Hash *temp = h[hash(a)].next;

    while (temp)
    {
        if (temp->p.x == a.x && temp->p.y == a.y)
            returntrue;
        temp = temp->next;
    }
    returnfalse;
}

void work()
{
    ans =0;
    for (int i =0; i < n -1; i++)
        for (int j = i +1; j < n; j++)
        {
            XPoint a, b;
            a.x = point[j].y - point[i].y + point[i].x;
            a.y = point[i].x - point[j].x + point[i].y;
            b.x = a.x + point[j].x - point[i].x;
            b.y = a.y + point[j].y - point[i].y;
            if (exist(a) && exist(b))
                ans++;
            a.x = point[i].x *2- a.x;
            a.y = point[i].y *2- a.y;
            b.x = a.x + point[j].x - point[i].x;
            b.y = a.y + point[j].y - point[i].y;
            if (exist(a) && exist(b))
                ans++;
        }
    ans /=4;
}

int main()
{
    //freopen("t.txt", "r", stdin);
while (scanf("%d", &n), n)
    {
        memset(h, 0, sizeof(h));
        input();
        work();
        printf("%d\n", ans);
    }
    return0;
}