题目描述与示例

题目描述

输入N个互不相同的二维整数坐标，求这N个坐标可以构成的正方形数量。[内积为零的的两个向量垂直]

题目练习网址：https://www.algomooc.com/problem/P2711

输入描述

第一行输入为N，N代表坐标数量，N为正整数。N <= 100

之后的 N 行输入为坐标x y以空格分隔，x，y为整数，-10 <= x, y <= 10

输出描述

输出可以构成的正方形数量。

示例一

输入

3
1 3
2 4
3 1

输出

0

说明

3个点不足以构成正方形

示例二

输入

4
0 0
1 2
3 1
2 -1

输出

1

解题思路

暴力解思路

一个正方形由4个顶点构成，暴力解的思路非常直接。

以4个点为一组，枚举所有这样的组，然后判断这些组是否可以构成正方形并且统计数量即可。

考虑这种思路的计算量，当N取最大值100时，一共需要枚举 $$C_n^4=C_{100}4≈10^8$$组。

用时间复杂度来考虑，这种做法四重for循环，复杂度为$$O(n^4)≈108$$，因此这样的暴力解思路必然在某些用例下超时。

故本篇题解对暴力解的做法略去不表。

根据对角线构建单个正方形

现在我们从考虑4个点降低到仅考虑2个点的情况。假设我们已知两个点P1和P2的坐标，分别记其坐标为(x1, y1)和(x2, y2)。

注意这两个点的选择是任意的，连接这两个点，我们可以做出如下的图

暂时无法在飞书文档外展示此内容

如果以这条线段作为某正方形的对角线，我们容易做出如下的图

暂时无法在飞书文档外展示此内容

我们可以得到P3和P4两个点，他们之间的连线线段P3P4是正方形的另一条对角线，和对角线P1P2互相垂直且长度相等。

当我们已知P1和P2的坐标(x1, y1)和(x2, y2)时，我们可以通过计算来算出正方形的另外两个点P3和P4的坐标(x3, y3)和(x4, y4)。

经过四个点，做出x轴或y轴的平行线，可以得到一个4条边平行于x轴和y轴的正方形以及4个全等三角形。设这4个全等三角形的两条直角边的长度分别为a和b，即有

暂时无法在飞书文档外展示此内容

结合P1和P2的坐标，我们可以得到如下图的数量关系。

暂时无法在飞书文档外展示此内容

容易列出方程组

$$\begin{cases} a + b = x_2 - x_1 \ a - b = y_2 - y_1 \end{cases}$$

其中a和b是未知数，x1, x2, y2, y2是已知量。容易解得

$$\begin{cases} a = \frac{(x_2 - x_1) + (y_2 - y_1)}{2} \ b = \frac{(x_2 - x_1) - (y_2 - y_1)}{2} \end{cases}$$

解出a和b之后，我们容易通过观察得到P3和P4的坐标。

暂时无法在飞书文档外展示此内容

P3的坐标为(x1+b, y1+a)。

暂时无法在飞书文档外展示此内容

P4的坐标为(x1+a, y1-b)。

写成代码即为

a = ((x2-x1) + (y2-y1)) / 2
b = ((x2-x1) - (y2-y1)) / 2
x3 = x1 + b
y3 = y1 + a
x4 = x1 + a
y4 = y1 - b

哈希集合判断是否存在正方形

在计算得到P3和P4的坐标之后，剩下的内容就显而易见了。

我们仅需要判断题目所给的所有的点的集合，P3、P4是否存在于这个集合中即可。

很容易想到，为了进行快速搜索，我们可以将原先的所有点储存在一个哈希集合points_set中。

n = int(input())
points_lst = list()
for _ in range(n):
    x, y = map(int, input().split())
    points_lst.append((x, y))

points_set = set(points_lst)

可以构建出如下的check()函数

def check(x1, x2, y1, y2, points_set):
    a = ((x2-x1) + (y2-y1)) / 2
    b = ((x2-x1) - (y2-y1)) / 2
    x3 = x1 + b
    y3 = y1 + a
    x4 = x1 + a
    y4 = y1 - b
    if (x3, y3) in points_set and (x4, y4) in points_set:
        return 1
    else:
        return 0

我们可以枚举所有的P1和P2，然后判断其对应的P3和P4是否存在，这样就尽可以用双重for循环来完成搜索的过程，将时间复杂度降到O(N^2)，这样就可以在N最大值取100的条件下通过本题了。

ans = 0

for i in range(n):
    x1, y1 = points_lst[i]
    for j in range(i+1, n):
        x2, y2 = points_lst[j]
        ans += check(x1, x2, y1, y2, points_set)

print(ans // 2)

注意，最终的答案ans必须整除2后再输出。

这是因为，在当前的遍历方式中，我们会在考虑P1P2构成的对角线时寻找对应的P3和P4点，也会在考虑以P3P4为对角线时找到P1和P2点。

换句话说，每一个可以构成的正方形，会被重复计算1次。

因此最终的答案必须整除2。

代码

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频


# 计算以P1P2线段作为对角线的正方形
# 计算出对应的P3和P4点
# 并且在哈希集合points_set中查找P3和P4点是否存在的函数
def check(x1, x2, y1, y2, points_set):
    # 计算出P3和P4点
    # 注意此处a和b的计算必须使用除法，而不是整除
    a = ((x2-x1) + (y2-y1)) / 2
    b = ((x2-x1) - (y2-y1)) / 2
    x3 = x1 + b
    y3 = y1 + a
    x4 = x1 + a
    y4 = y1 - b
    # 如果P3和P4点均位于哈希集合中，则找到一个正方形，返回1
    if (x3, y3) in points_set and (x4, y4) in points_set:
        return 1
    # 否则返回0
    else:
        return 0

# 输入
n = int(input())
points_lst = list()
# 遍历n次，将输入的坐标点存入列表points_lst中
for _ in range(n):
    x, y = map(int, input().split())
    points_lst.append((x, y))

# 将列表points_lst中的坐标点存入哈希集合points_set中
points_set = set(points_lst)

# 初始化答案变量ans
ans = 0
# 两两一组，遍历points_lst中的坐标点，计算以P1P2线段作为对角线的正方形
for i in range(n):
    x1, y1 = points_lst[i]
    for j in range(i+1, n):
        x2, y2 = points_lst[j]
        # 调用check函数，计算以P1P2线段作为对角线的正方形
        # 返回值为1或0，将结果递增在ans中
        ans += check(x1, x2, y1, y2, points_set)

# 由于在当前遍历方式下，每一个正方形被计算了2次
# 因此最终结果必须除以2后输出
print(ans // 2)

Java

import java.util.*;

public class Main {
    // 计算以 (x1, y1) 和 (x2, y2) 作为对角线的正方形
    public static int check(int x1, int y1, int x2, int y2, Set<String> pointsSet) {
        // 计算两个关键值
        int delta1 = (x2 - x1) + (y2 - y1);
        int delta2 = (x2 - x1) - (y2 - y1);

        // 如果 delta1 或 delta2 不能被2整除，则返回0，避免非整数坐标
        if (delta1 % 2 != 0 || delta2 % 2 != 0) {
            return 0;
        }

        // 计算 P3 和 P4 坐标
        int a = delta1 / 2;
        int b = delta2 / 2;

        int x3 = x1 + b;
        int y3 = y1 + a;
        int x4 = x1 + a;
        int y4 = y1 - b;

        // 生成哈希集合的查询字符串（确保整数计算）
        String key3 = x3 + "," + y3;
        String key4 = x4 + "," + y4;

        // 检查 P3 和 P4 是否在哈希集合中
        if (pointsSet.contains(key3) && pointsSet.contains(key4)) {
            return 1;
        }
        return 0;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 读取点的个数

        List<int[]> pointsList = new ArrayList<>();
        Set<String> pointsSet = new HashSet<>();

        // 读取坐标点
        for (int i = 0; i < n; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            pointsList.add(new int[]{x, y});
            pointsSet.add(x + "," + y); // 存入哈希集合，方便快速查询
        }
        scanner.close();

        int ans = 0;

        // 两两组合计算以 P1P2 作为对角线的正方形
        for (int i = 0; i < n; i++) {
            int x1 = pointsList.get(i)[0];
            int y1 = pointsList.get(i)[1];

            for (int j = i + 1; j < n; j++) {
                int x2 = pointsList.get(j)[0];
                int y2 = pointsList.get(j)[1];

                ans += check(x1, y1, x2, y2, pointsSet);
            }
        }

        // 由于每个正方形被计算了2次，因此最终结果除以2
        System.out.println(ans / 2);
    }
}

C++

#include <iostream>
#include <unordered_set>
#include <vector>
#include <sstream>

using namespace std;

// 计算以 (x1, y1) 和 (x2, y2) 作为对角线的正方形
int check(int x1, int y1, int x2, int y2, unordered_set<string> &pointsSet) {
    // 计算 P3 和 P4
    double a = ((x2 - x1) + (y2 - y1)) / 2.0;
    double b = ((x2 - x1) - (y2 - y1)) / 2.0;

    double x3 = x1 + b;
    double y3 = y1 + a;
    double x4 = x1 + a;
    double y4 = y1 - b;

    // 构造哈希集合的查询字符串
    stringstream ss1, ss2;
    ss1 << x3 << "," << y3;
    ss2 << x4 << "," << y4;

    // 检查 P3 和 P4 是否在哈希集合中
    if (pointsSet.count(ss1.str()) && pointsSet.count(ss2.str())) {
        return 1;
    }
    return 0;
}

int main() {
    int n;
    cin >> n;

    vector<pair<int, int>> pointsList;
    unordered_set<string> pointsSet;

    // 读取坐标点
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        pointsList.emplace_back(x, y);

        stringstream ss;
        ss << x << "," << y;
        pointsSet.insert(ss.str());
    }

    int ans = 0;

    // 两两组合计算以 P1P2 作为对角线的正方形
    for (int i = 0; i < n; i++) {
        int x1 = pointsList[i].first;
        int y1 = pointsList[i].second;

        for (int j = i + 1; j < n; j++) {
            int x2 = pointsList[j].first;
            int y2 = pointsList[j].second;

            ans += check(x1, y1, x2, y2, pointsSet);
        }
    }

    // 由于每个正方形被计算了2次，因此最终结果除以2
    cout << ans / 2 << endl;

    return 0;
}

C

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

#define MAX_POINTS 100  // 假设最多 100 个点
#define HASH_SIZE 10007 // 设定哈希表大小（素数，减少哈希冲突）

// 定义存储点的结构体
typedef struct {
    int x, y;
} Point;

// 哈希表存储结构
typedef struct HashNode {
    char key[20]; // 存储坐标的字符串，例如 "3,4"
    struct HashNode* next;
} HashNode;

// 哈希表
HashNode* hashTable[HASH_SIZE];

// 计算哈希值（字符串哈希函数）
unsigned int hashFunction(const char* key) {
    unsigned int hash = 5381;
    while (*key) {
        hash = ((hash << 5) + hash) + (*key++); // hash * 33 + c
    }
    return hash % HASH_SIZE;
}

// 在哈希表中插入键值
void insertHashTable(const char* key) {
    unsigned int index = hashFunction(key);
    HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
    strcpy(newNode->key, key);
    newNode->next = hashTable[index];
    hashTable[index] = newNode;
}

// 查找哈希表是否包含某个键
int containsHashTable(const char* key) {
    unsigned int index = hashFunction(key);
    HashNode* node = hashTable[index];
    while (node) {
        if (strcmp(node->key, key) == 0) {
            return 1; // 存在
        }
        node = node->next;
    }
    return 0; // 不存在
}

// 计算以 (x1, y1) 和 (x2, y2) 作为对角线的正方形
int check(int x1, int y1, int x2, int y2) {
    // 计算两个关键值
    int delta1 = (x2 - x1) + (y2 - y1);
    int delta2 = (x2 - x1) - (y2 - y1);

    // 如果 delta1 或 delta2 不能被 2 整除，则返回 0，避免非整数坐标
    if (delta1 % 2 != 0 || delta2 % 2 != 0) {
        return 0;
    }

    // 计算 P3 和 P4 坐标
    int a = delta1 / 2;
    int b = delta2 / 2;

    int x3 = x1 + b;
    int y3 = y1 + a;
    int x4 = x1 + a;
    int y4 = y1 - b;

    // 生成哈希表键（字符串形式存储坐标）
    char key3[20], key4[20];
    sprintf(key3, "%d,%d", x3, y3);
    sprintf(key4, "%d,%d", x4, y4);

    // 检查 P3 和 P4 是否在哈希集合中
    return containsHashTable(key3) && containsHashTable(key4);
}

int main() {
    int n;
    scanf("%d", &n); // 读取点的个数

    Point pointsList[MAX_POINTS];  // 存储所有点的数组

    // 读取坐标点
    for (int i = 0; i < n; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        pointsList[i].x = x;
        pointsList[i].y = y;

        // 计算哈希键并存入哈希表
        char key[20];
        sprintf(key, "%d,%d", x, y);
        insertHashTable(key);
    }

    int ans = 0;

    // 两两组合计算以 P1P2 作为对角线的正方形
    for (int i = 0; i < n; i++) {
        int x1 = pointsList[i].x;
        int y1 = pointsList[i].y;

        for (int j = i + 1; j < n; j++) {
            int x2 = pointsList[j].x;
            int y2 = pointsList[j].y;

            ans += check(x1, y1, x2, y2);
        }
    }

    // 由于每个正方形被计算了 2 次，因此最终结果除以 2
    printf("%d\n", ans / 2);

    return 0;
}

Node JavaScript

const readline = require("readline");

// 创建接口用于读取输入
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let n = 0;
const pointsList = [];
const pointsSet = new Set();

// 读取输入
rl.on("line", (line) => {
  if (n === 0) {
    n = parseInt(line); // 读取点的个数
  } else {
    const [x, y] = line.split(" ").map(Number);
    pointsList.push([x, y]);
    pointsSet.add(`${x},${y}`); // 存入哈希集合，方便快速查询

    if (pointsList.length === n) {
      rl.close();
    }
  }
});

// 计算以 (x1, y1) 和 (x2, y2) 作为对角线的正方形
function check(x1, y1, x2, y2, pointsSet) {
  const delta1 = (x2 - x1) + (y2 - y1);
  const delta2 = (x2 - x1) - (y2 - y1);

  // 如果 delta1 或 delta2 不能被2整除，则返回0，避免非整数坐标
  if (delta1 % 2 !== 0 || delta2 % 2 !== 0) {
    return 0;
  }

  // 计算 P3 和 P4 坐标
  const a = delta1 / 2;
  const b = delta2 / 2;

  const x3 = x1 + b;
  const y3 = y1 + a;
  const x4 = x1 + a;
  const y4 = y1 - b;

  // 生成哈希集合的查询字符串（确保整数计算）
  const key3 = `${x3},${y3}`;
  const key4 = `${x4},${y4}`;

  // 检查 P3 和 P4 是否在哈希集合中
  return pointsSet.has(key3) && pointsSet.has(key4) ? 1 : 0;
}

rl.on("close", () => {
  let ans = 0;

  // 两两组合计算以 P1P2 作为对角线的正方形
  for (let i = 0; i < n; i++) {
    const [x1, y1] = pointsList[i];

    for (let j = i + 1; j < n; j++) {
      const [x2, y2] = pointsList[j];

      ans += check(x1, y1, x2, y2, pointsSet);
    }
  }

  // 由于每个正方形被计算了2次，因此最终结果除以2
  console.log(Math.floor(ans / 2));
});

Go

package main

import (
        "bufio"
        "fmt"
        "os"
        "strconv"
        "strings"
)

// 计算以 (x1, y1) 和 (x2, y2) 作为对角线的正方形
func check(x1, y1, x2, y2 int, pointsSet map[string]bool) int {
        delta1 := (x2 - x1) + (y2 - y1)
        delta2 := (x2 - x1) - (y2 - y1)

        // 如果 delta1 或 delta2 不能被2整除，则返回0，避免非整数坐标
        if delta1%2 != 0 || delta2%2 != 0 {
                return 0
        }

        // 计算 P3 和 P4 坐标
        a := delta1 / 2
        b := delta2 / 2

        x3 := x1 + b
        y3 := y1 + a
        x4 := x1 + a
        y4 := y1 - b

        // 生成哈希集合的查询字符串（确保整数计算）
        key3 := fmt.Sprintf("%d,%d", x3, y3)
        key4 := fmt.Sprintf("%d,%d", x4, y4)

        // 检查 P3 和 P4 是否在哈希集合中
        if pointsSet[key3] && pointsSet[key4] {
                return 1
        }
        return 0
}

func main() {
        scanner := bufio.NewScanner(os.Stdin)

        var n int
        pointsList := make([][2]int, 0) // 存储所有点
        pointsSet := make(map[string]bool) // 存储点的哈希集合，方便快速查找

        // 读取点的个数
        if scanner.Scan() {
                n, _ = strconv.Atoi(scanner.Text())
        }

        // 读取坐标点
        for i := 0; i < n; i++ {
                if scanner.Scan() {
                        line := scanner.Text()
                        parts := strings.Split(line, " ")
                        x, _ := strconv.Atoi(parts[0])
                        y, _ := strconv.Atoi(parts[1])
                        pointsList = append(pointsList, [2]int{x, y})
                        pointsSet[fmt.Sprintf("%d,%d", x, y)] = true
                }
        }

        ans := 0

        // 两两组合计算以 P1P2 作为对角线的正方形
        for i := 0; i < n; i++ {
                x1, y1 := pointsList[i][0], pointsList[i][1]

                for j := i + 1; j < n; j++ {
                        x2, y2 := pointsList[j][0], pointsList[j][1]

                        ans += check(x1, y1, x2, y2, pointsSet)
                }
        }

        // 由于每个正方形被计算了2次，因此最终结果除以2
        fmt.Println(ans / 2)
}

时空复杂度

时间复杂度：O(N^2)。双重循环所需时间复杂度。

空间复杂度：O(N)。哈希集合所占空间。