刷题笔记合集🔗

构成正方形的数量

问题描述

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

输入格式

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

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

输出格式

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

样例输入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);
            int x6 = x2 + (y1 - y2);
            int y6 = y2 - (x1 - x2);

            // 构造第二组两个点的字符串表示
            char p5[MAX_POINT_LEN], p6[MAX_POINT_LEN];
            snprintf(p5, MAX_POINT_LEN, "%d %d", x5, y5);
            snprintf(p6, MAX_POINT_LEN, "%d %d", x6, y6);

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

    // 每个正方形被计算了4次，所以返回时需要除以4
    return count / 4;
}

int main() {
    int n;
    // 读取点的数量
    scanf("%d", &n);
    getchar(); // 忽略换行符

    // 创建点数组
    char points[MAX_POINTS][MAX_POINT_LEN];

    // 读取每个点的坐标
    for (int i = 0; i < n; i++) {
        fgets(points[i], MAX_POINT_LEN, stdin);
        // 移除每个点末尾的换行符
        points[i][strcspn(points[i], "\n")] = 0;
    }

    // 计算并输出结果
    int result = countSquares(points, n);
    printf("%d\n", result);

    return 0;
}

• Javascript

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let n = 0;
const points = [];

rl.on('line', (line) => {
    if (n === 0) {
        n = parseInt(line);
    } else {
        points.push(line);
        if (points.length === n) {
            const result = countSquares(points);
            console.log(result);
            rl.close();
        }
    }
});

function countSquares(points) {
    const pointSet = new Set(points);
    let count = 0;

    for (let i = 0; i < points.length; i++) {
        for (let j = i + 1; j < points.length; j++) {
            const [x1, y1] = points[i].split(' ').map(Number);
            const [x2, y2] = points[j].split(' ').map(Number);

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

            // 检查这两个点是否在点集中
            if (pointSet.has(`${x3} ${y3}`) && pointSet.has(`${x4} ${y4}`)) {
                count++;
            }

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

            // 检查这两个点是否在点集中
            if (pointSet.has(`${x5} ${y5}`) && pointSet.has(`${x6} ${y6}`)) {
                count++;
            }
        }
    }

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

• Java

import java.util.*;

public class Main {
    public static int countSquares(List<String> points) {
        Set<String> pointSet = new HashSet<>(points);
        int count = 0;
        
        for (int i = 0; i < points.size(); i++) {
            for (int j = i + 1; j < points.size(); j++) {
                String[] p1 = points.get(i).split(" ");
                String[] p2 = points.get(j).split(" ");
                int x1 = Integer.parseInt(p1[0]), y1 = Integer.parseInt(p1[1]);
                int x2 = Integer.parseInt(p2[0]), y2 = Integer.parseInt(p2[1]);
                
                // 计算第一组可能的正方形点
                int x3 = x1 - (y1 - y2);
                int y3 = y1 + (x1 - x2);
                int x4 = x2 - (y1 - y2);
                int y4 = y2 + (x1 - x2);
                
                // 检查这两个点是否在点集中
                if (pointSet.contains(x3 + " " + y3) && pointSet.contains(x4 + " " + y4)) {
                    count++;
                }
                
                // 计算第二组可能的正方形点
                int x5 = x1 + (y1 - y2);
                int y5 = y1 - (x1 - x2);
                int x6 = x2 + (y1 - y2);
                int y6 = y2 - (x1 - x2);
                
                // 检查这两个点是否在点集中
                if (pointSet.contains(x5 + " " + y5) && pointSet.contains(x6 + " " + y6)) {
                    count++;
                }
            }
        }
        
        // 由于每个正方形被计算了4次，所以需要除以4
        return count / 4;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        List<String> points = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            points.add(scanner.nextLine());
        }
        
        int result = countSquares(points);
        System.out.println(result);
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <unordered_set>
#include <string>

using namespace std;

int countSquares(const vector<string>& points) {
    unordered_set<string> pointSet(points.begin(), points.end());
    int count = 0;
    int n = points.size();

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int x1, y1, x2, y2;
            sscanf(points[i].c_str(), "%d %d", &x1, &y1);
            sscanf(points[j].c_str(), "%d %d", &x2, &y2);
            
            // 计算第一组可能的正方形点
            int x3 = x1 - (y1 - y2);
            int y3 = y1 + (x1 - x2);
            int x4 = x2 - (y1 - y2);
            int y4 = y2 + (x1 - x2);
            
            // 检查这两个点是否在点集中
            string p3 = to_string(x3) + " " + to_string(y3);
            string p4 = to_string(x4) + " " + to_string(y4);
            if (pointSet.count(p3) && pointSet.count(p4)) {
                ++count;
            }
            
            // 计算第二组可能的正方形点
            int x5 = x1 + (y1 - y2);
            int y5 = y1 - (x1 - x2);
            int x6 = x2 + (y1 - y2);
            int y6 = y2 - (x1 - x2);
            
            // 检查这两个点是否在点集中
            string p5 = to_string(x5) + " " + to_string(y5);
            string p6 = to_string(x6) + " " + to_string(y6);
            if (pointSet.count(p5) && pointSet.count(p6)) {
                ++count;
            }
        }
    }

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

int main() {
    int n;
    cin >> n;
    cin.ignore(); // 忽略换行符

    vector<string> points(n);
    for (int i = 0; i < n; ++i) {
        getline(cin, points[i]);
    }

    int result = countSquares(points);
    cout << result << endl;

    return 0;
}