1 solutions

  • 0
    @ 9 months ago

    题目大意

    给出的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); // 输出结果
        }
    }
    
    
    • 1

    2022.10.16-秋招-构成正方形的数量

    Information

    ID
    38
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    4
    Tags
    # Submissions
    15
    Accepted
    7
    Uploaded By