【最新华为OD机试E卷】构成正方形的数量(100分)

🍭 大家好这里是春秋招笔试突围 ，一枚热爱算法的程序员

💻 ACM金牌🏅️团队 ｜ 大厂实习经历 ｜ 多年算法竞赛经历

✨ 本系列打算持续跟新华为OD-E/D卷的多语言AC题解

🧩 大部分包含 Python / C / Javascript / Java / Cpp 多语言代码

👏 感谢大家的订阅➕ 和 喜欢💗 和手里的小花花🌸

最新华为OD机试E卷全、新、准，题目覆盖率达 95% 以上，其中D卷题目全部支持在线评测，E卷题目正在持续上线中~

最新华为OD机试专栏: https://www.nowcoder.com/creation/manager/columnDetail/MgbyJj

🎀关于华为OD

• ✨华为OD的概念 华为的大部分社会招聘采用了被称为OD（Outsourcing Dispatch）模式，这是一种与德科共同进行的招聘方式。在这种模式下，被招聘的员工通常被定级在13至17级，这些员工被视为华为的储备人才。华为每年会从这些OD项目中选拔表现出色的员工，并将他们转为正式员工。
• ⌚️华为 OD 应聘流程

  • 第一步：投递简历

    • 提供姓名、邮箱、手机号、身份证号，用于锁定，所以投递前需要考虑清楚，投到项目组之后，一般不会转给另一个项目的 HR 了，也就是被锁定。

  • 第二步：机试

    • 3 道算法题，400 分满分，一般 1 个月的准备时间，华为机试必须要 150 分以上，没有过半年之后才能参加下一次考试。

  • 第三步：技术面

    • 2 轮技术面试。

  • 第四步：HR 与主管面试

  • 第五步：录用，发 offer

🍓OJ题目截图

💟 构成正方形的数量

问题描述

给定 个互不相同的二维整数坐标点，求这 个坐标点可以构成的正方形数量。需要注意的是，两个向量的内积为零时，这两个向量垂直。

输入格式

第一行输入一个正整数 ，表示坐标点的数量。

接下来的 行，每行包含两个整数 和 ，以空格分隔，表示一个坐标点 。

输出格式

输出一个整数，表示可以构成的正方形数量。

样例输入1

3
1 3
2 4
3 1

样例输出1

0

样例输入2

4
0 0
1 2
3 1
2 -1

样例输出2

1

样例解释

数据范围

题解

这道题目要求我们计算给定的 个点中可以构成的正方形数量。解决这个问题的关键在于理解正方形的性质和如何利用坐标系中的点来判断正方形。

首先，我们需要明白，一个正方形可以由任意两个点确定。当我们知道正方形的一条边（即两个点的坐标）时，我们就可以计算出其他两个点的坐标。

解题思路如下：

1. 枚举任意两个点作为正方形的一条边。
2. 根据这两个点，计算出可能的其他两个点的坐标。
3. 检查计算出的点是否在给定的点集中。
4. 如果所有四个点都在点集中，则找到了一个正方形。

参考代码

• Python

def count_squares(points):
    # 将点集转换为集合，方便快速查找
    point_set = set(points)
    n = len(points)
    count = 0

    # 枚举所有可能的点对
    for i in range(n):
        for j in range(i + 1, n):
            x1, y1 = map(int, points[i].split())
            x2, y2 = map(int, points[j].split())
            
            # 计算第一组可能的正方形点
            x3 = x1 - (y1 - y2)
            y3 = y1 + (x1 - x2)
            x4 = x2 - (y1 - y2)
            y4 = y2 + (x1 - x2)
            
            # 检查这两个点是否在点集中
            if f"{x3} {y3}" in point_set and f"{x4} {y4}" in point_set:
                count += 1

            # 计算第二组可能的正方形点
            x5 = x1 + (y1 - y2)
            y5 = y1 - (x1 - x2)
            x6 = x2 + (y1 - y2)
            y6 = y2 - (x1 - x2)
            
            # 检查这两个点是否在点集中
            if f"{x5} {y5}" in point_set and f"{x6} {y6}" in point_set:
                count += 1

    # 由于每个正方形被计算了4次，所以需要除以4
    return count // 4

# 读取输入
n = int(input())
points = [input() for _ in range(n)]

# 计算并输出结果
result = count_squares(points)
print(result)

• C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义点的最大数量
#define MAX_POINTS 1000
// 定义单个点的字符串长度 (例如 "123 456")
#define MAX_POINT_LEN 20

// 字符串集合结构体
typedef struct {
    char points[MAX_POINTS][MAX_POINT_LEN]; // 存储点的字符串
    int size; // 集合中的点数量
} PointSet;

// 初始化点集合
void initPointSet(PointSet *set) {
    set->size = 0;
}

// 向点集合中添加一个点
void addPoint(PointSet *set, const char *point) {
    strcpy(set->points[set->size], point);
    set->size++;
}

// 检查集合中是否包含指定的点
int containsPoint(PointSet *set, const char *point) {
    for (int i = 0; i < set->size; i++) {
        if (strcmp(set->points[i], point) == 0) {
            return 1; // 找到匹配的点
        }
    }
    return 0; // 未找到匹配的点
}

// 计算可能的正方形数量
int countSquares(char points[MAX_POINTS][MAX_POINT_LEN], int n) {
    PointSet pointSet;
    initPointSet(&pointSet);

    // 将所有点添加到集合中
    for (int i = 0; i < n; i++) {
        addPoint(&pointSet, points[i]);
    }

    int count = 0;

    // 遍历所有可能的点对 (i, j)
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int x1, y1, x2, y2;
            sscanf(points[i], "%d %d", &x1, &y1); // 从第一个点获取坐标
            sscanf(points[j], "%d %d", &x2, &y2); // 从第二个点获取坐标

            // 计算第一组可能的正方形点
            int x3 = x1 - (y1 - y2);
            int y3 = y1 + (x1 - x2);
            int x4 = x2 - (y1 - y2);
            int y4 = y2 + (x1 - x2);

            // 构造两个点的字符串表示
            char p3[MAX_POINT_LEN], p4[MAX_POINT_LEN];
            snprintf(p3, MAX_POINT_LEN, "%d %d", x3, y3);
            snprintf(p4, MAX_POINT_LEN, "%d %d", x4, y4);

            // 检查这两个点是否存在于集合中
            if (containsPoint(&pointSet, p3) && containsPoint(&pointSet, p4)) {
                count++;
            }

            // 计算第二组可能的正方形点
            int x5 = x1 + (y1 - y2);
            int y5 = y1 - (x1 - x2);
            in