题目描述

在地图上散落着 n 个车轮, 小 J 想用它们造一辆车. 要求如下:

  1. 一辆车需要四个车轮, 且四个车轮构成一个正方形

  2. 车轮不能移动

你需要计算有多少种造车的方案 (两个方案不同当且仅当所用车轮不全相同, 坐标相同的两个车轮视为不同车轮).

输入格式

第一行一个整数 \(n\)

接下来 \(n\) 行, 每行两个整数 \(x\)\(y\), 表示在 \((x,y)\) 处有一个车轮

输出格式

一行一个整数, 表示方案数

样例输入

9
0 0
1 0
2 0
0 2
1 2
2 2
0 1
1 1
2 1

样例输出

6

数据范围

30% 的数据保证 \(n \leq 30\)

100% 的数据保证 \(1 \leq n \leq 1000\);\(|x|, |y| \lt 20000\)

Explanation

用二维 map 维护结点数量.

然后就没有然后了.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <set>
#include <map>

using namespace std;
typedef long long lli;
const int maxn = 1010;

class CoordinatesLocatingManager
{
public:
    map<int, map<int, lli> > loc;
    void insert(int x, int y)
    {
        if (loc.find(y) == loc.end()) {
            map<int, lli> new_mp;
            loc[y] = new_mp;
        }
        map<int, lli>& mp = loc[y];
        if (mp.find(x) == mp.end())
            mp[x] = 1;
        else
            mp[x]++;
        return ;
    }
    lli query(int x, int y)
    {
        if (loc.find(y) == loc.end())
            return 0;
        map<int, lli>& mp = loc[y];
        if (mp.find(x) == mp.end())
            return 0;
        return mp[x];
    }
    void flush(int &n, lli arr[][3])
    {
        n = 0;
        for (map<int, map<int, lli> >::iterator i = loc.begin(); i != loc.end(); i++) {
            map<int, lli>& mp = i->second;
            for (map<int, lli>::iterator j = mp.begin(); j != mp.end(); j++) {
                arr[++n][0] = j->first;
                arr[n][1] = i->first;
                arr[n][2] = j->second;
            }
        }
        return ;
    }
} clm;

int n, m;
lli arr[maxn][3]; // X axis, Y axis, count

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1, a, b; i <= n; i++) {
        scanf("%d%d", &a, &b);
        clm.insert(a, b);
    }
    clm.flush(m, arr);
    // Done reading data, now doing the following things:
    // Take out every diagonal line, and test if the coords are okay
    lli res = 0;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j < i; j++) {
            int x1 = arr[i][0], y1 = arr[i][1],
                x2 = arr[j][0], y2 = arr[j][1];
            lli c1 = arr[i][2],
                c2 = arr[j][2];
            // Calculating the coords of the remaining two points
            int x3 = x1 + x2 + y1 - y2,
                y3 = x2 - x1 + y1 + y2,
                x4 = x1 + x2 - y1 + y2,
                y4 = x1 - x2 + y1 + y2;
            if (x3 % 2 == 1 || y3 % 2 == 1 || x4 % 2 == 1 || y4 % 2 == 1)
                continue;
            x3 /= 2, y3 /= 2, x4 /= 2, y4 /= 2;
            // Locating the two new points
            lli c3 = clm.query(x3, y3),
                c4 = clm.query(x4, y4);
            // printf("(%d, %d: %d), (%d, %d: %d), (%d, %d: %d), (%d, %d: %d) => %d\n",
            //     x1, y1, c1, x2, y2, c2, x3, y3, c3, x4, y4, c4, c1*c2*c3*c4);
            res += c1 * c2 * c3 * c4;
        }
    res /= 2;
    printf("%lld\n", res);
    return 0;
}