ACM模版

描述

题解

都怪我英语不好,更怪百度翻译个信球,硬生生将正方形给我翻译成了正多边形,导致一上来我就写了一个 搜索 + 凸包 + 判边……后来才发现,我读错题了!!!

这个题需要用到二维平面 HASH 解决,之所以要用到 HASH 是因为我们只需要枚举两个点构成的一条边就能获取另外一条对边,所以呢,我们要判断这条对边的两个顶点是否存在,如果存在说明存在,最后注意除以 4 <script type="math/tex" id="MathJax-Element-50">4</script>,因为正方形的每条边我们都算过一次了。

代码

#include <iostream>
#include <cstring>

using namespace std;

const int MAXN = 1000;

struct Node
{
    int x, y;
};

struct hashTable
{
    int x, y;
    hashTable *next;

    hashTable()
    {
        next = 0;
    }
};

Node pos[MAXN];
hashTable *_hash[MAXN << 1];

void insert(int k)
{
    int key = ((pos[k].x * pos[k].x) + (pos[k].y * pos[k].y)) % MAXN + 1;

    if (!_hash[key])
    {
        hashTable *temp = new hashTable;
        temp->x = pos[k].x;
        temp->y = pos[k].y;
        _hash[key] = temp;
    }
    else
    {
        hashTable *temp = _hash[key];

        while (temp->next)
        {
            temp = temp->next;
        }

        temp->next = new hashTable;
        temp->next->x = pos[k].x;
        temp->next->y = pos[k].y;
    }
}

bool find(int x, int y)
{
    int key = (x * x + y * y) % MAXN + 1;

    if (!_hash[key])
    {
        return false;
    }
    else
    {
        hashTable *temp = _hash[key];

        while (temp)
        {
            if (temp->x == x && temp->y == y)
            {
                return true;
            }

            temp = temp->next;
        }
    }

    return false;
}

int main()
{
    int n;
    while (cin >> n)
    {
        memset(_hash, 0, sizeof(_hash));

        for (int k = 1; k <= n; k++)
        {
            cin >> pos[k].x >> pos[k].y;
            insert(k);
        }

        int res = 0;
        for (int i = 1; i <= n - 1; i++)
        {
            for (int j = i + 1; j <= n; j++)
            {
                int a = pos[j].x - pos[i].x;
                int b = pos[j].y - pos[i].y;

                int x3 = pos[i].x + b;
                int y3 = pos[i].y - a;
                int x4 = pos[j].x + b;
                int y4 = pos[j].y - a;

                if (find(x3, y3) && find(x4, y4))
                {
                    res++;
                }

                x3 = pos[i].x - b;
                y3 = pos[i].y + a;
                x4 = pos[j].x - b;
                y4 = pos[j].y + a;

                if (find(x3, y3) && find(x4, y4))
                {
                    res++;
                }
            }
        }

        cout << res / 4 << endl;
    }

    return 0;
}