题目大意

给出的n个向量能构成多少个多少个正方形

思路

思路: 计算几何

1.表示点：

将每个输入的点表示为二维坐标，并将其存储在一个集合中，以便快速查找。

2.选择两点作为边的端点：

从给定的点中选择两个不同的点 A 和 B，这两点将作为正方形的一条边。

3.计算正方形的其他两个点：

通过对这两个点的坐标进行计算，确定第三个点 C 和第四个点 D。这个过程基于正方形的几何性质： 点 C 的坐标可以通过调整A 和 B 的坐标来获得，使得 A 和 C 垂直于 A 和 B。 点 D 也通过类似的方式计算，确保 B 和 D 垂直。

4.检查点是否存在：

检查计算出的 C 和 D 是否在输入的点集合中。如果这两个点都在集合中，那么就可以确定 A,B,C,D 可以构成一个正方形。

5.避免重复计数：

因为每个正方形的四条边都可能被计算多次，因此最终的计数需要除以 4，以消除重复。

代码

C++代码

#include <bits/stdc++.h>

using namespace std;

// 定义一个类型 PII 为一个整型对，方便表示坐标点
typedef pair<int, int> PII;
#define x first  // 将 first 定义为 x
#define y second // 将 second 定义为 y

// 主函数，处理逻辑
void solve() {
    int n; // 点的数量
    cin >> n; // 输入点的数量
    vector<PII> a(n); // 存储点的数组
    set<PII> sett; // 使用集合存储点，方便查找

    // 输入点的坐标
    for (int i = 0; i < n; ++i) {
        cin >> a[i].x >> a[i].y; // 输入每个点的坐标
        sett.insert(a[i]); // 将点插入集合中
    }

    int ans = 0; // 记录正方形的数量
    
    // 定义一个 lambda 函数，用于计算第三个点
    function<PII(const PII&, const PII&)> get_z = [](const PII&p1, const PII&p2) -> PII {
        // 根据两个点计算第三个点的坐标
    	return {p2.x + p2.y - p1.y, p2.y - (p2.x - p1.x)};
    };

    // 遍历所有点的组合，寻找能构成正方形的点
    for (const PII &x : a) {
        for (const PII &y : a) {
            if (x != y) { // 确保 x 和 y 不同
                PII z = get_z(x, y); // 计算第三个点 z
                // 检查 z 和第四个点是否在集合中
                if (sett.count(z) && sett.count(get_z(y, z))) {
                    ans += 1; // 找到一个正方形，计数
                }
            }
        }
    }

    // 因为每个正方形会被计算四次，所以最后结果除以 4
    cout << ans / 4 << endl;
}

// 程序入口
int main() {
    solve(); // 调用解题函数
    return 0; // 返回 0，表示程序正常结束
}

python代码

def solve():
    n = int(input())  # 输入点的数量
    a = [(0, 0)] * n  # 初始化点的列表，使用元组表示坐标
    ans = 0  # 初始化正方形的计数

    # 输入每个点的坐标
    for i in range(n):
        a[i] = tuple(map(int, input().split()))  # 将输入的坐标转换为元组并存储在列表中

    sett = set(a)  # 使用集合存储点，以便快速查找

    # 定义一个函数，用于计算正方形的第三个点
    def get_z(x, y):
        return (y[0] + y[1] - x[1], y[1] - (y[0] - x[0]))  # 根据点 x 和 y 计算点 z 的坐标

    # 遍历所有点的组合，寻找能构成正方形的点
    for x in a:
        for y in a:
            if x != y:  # 确保 x 和 y 不同
                z = get_z(x, y)  # 计算第三个点 z
                # 检查 z 和第四个点是否在集合中
                if z in sett and get_z(y, z) in sett:
                    ans += 1  # 找到一个正方形，计数加一

    # 因为每个正方形会被计算四次，所以最后结果除以 4
    print(ans // 4)

# 程序入口
if __name__ == "__main__":
    solve()  # 调用解题函数

Java代码

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    // 定义一个点的类
    static class Point {
        int x, y; // 点的坐标

        // 构造函数
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        // 重写 equals 方法，以便比较两个点是否相等
        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true; // 自身比较
            if (obj == null || getClass() != obj.getClass()) return false; // 检查类型
            Point other = (Point) obj; // 类型转换
            return x == other.x && y == other.y; // 比较坐标
        }

        // 重写 hashCode 方法，以便在 HashSet 中正确使用
        @Override
        public int hashCode() {
            return 31 * x + y; // 根据 x 和 y 计算哈希值
        }
    }

    public static void main(String[] args) {
        solve(); // 调用解决方案
    }
    
    // 计算正方形的第三个点
    public static Point get_z(Point x, Point y) {
        // 根据点 x 和 y 计算点 z 的坐标
        return new Point(y.x + y.y - x.y, y.y - (y.x - x.x));
    }

    static void solve() {
        Scanner sc = new Scanner(System.in); // 创建扫描器以读取输入
        int n = sc.nextInt(); // 输入点的数量
        Point[] a = new Point[n]; // 创建存储点的数组

        // 输入每个点的坐标
        for (int i = 0; i < n; ++i) {
            int x = sc.nextInt(); // 读取 x 坐标
            int y = sc.nextInt(); // 读取 y 坐标
            a[i] = new Point(x, y); // 创建点并存储在数组中
        }

        Set<Point> sett = new HashSet<>(); // 使用 HashSet 存储点，以便快速查找
        for (Point p : a) {
            sett.add(p); // 将每个点添加到集合中
        }

        int ans = 0; // 初始化正方形的计数

        // 遍历所有点的组合，寻找能构成正方形的点
        for (Point x : a) {
            for (Point y : a) {
                if (!x.equals(y)) { // 确保 x 和 y 不同
                    Point z = get_z(x, y); // 计算第三个点 z
                    
                    // 检查 z 和通过 y 计算得到的第四个点是否在集合中
                    if (sett.contains(z) && sett.contains(get_z(y, z))) {
                        ans += 1; // 找到一个正方形，计数加一
                    }
                }
            }
        }

        // 因为每个正方形会被计算四次，所以最后结果除以 4
        System.out.println(ans / 4); // 输出结果
    }
}