构成正方形的数量

真题目录: 点击去查看

E 卷 100分题型

题目描述

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

输入描述

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

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

输出描述

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

示例1

输入

3
1 3
2 4
3 1

输出

0

说明

（3个点不足以构成正方形）

示例2

输入

4
0 0
1 2
3 1
2 -1

输出

1

题解

思路：
利用的是正方形中的边的向量关系进行求解。假设A(x1, y1)和B(x2,y2)是正方形的两条边。 组成的向量AB为{x2- x1, y2 - y1}。
注意向量旋转的两个公式：

逆时针旋转90°, （x, y） -> (-y, x)
顺时针旋转180°, （x, y） -> (y, -x)

情况一：(图画的不是很准确应该是正方形的)

BA向量的值为{x1-x2, y1-y2}, 逆时针旋转可以得出AD、BC向量的值 => x3 = x1 - (y1 - y2), y3 = y1 + (x1 - x2), x4=x2 - (y1 - y2), y4= y2 + (x1 - x2)

情况二：(图画的不是很准确应该是正方形的)

可以推导出x3 = x2 + (y1 - y2), y3=y2 - (x1 - x2), x4=x1+(y1-y2), y4=y3 - (x1 - x2)

根据上述推到过程，可以枚举两个点，然后去判断两外两个点是否存在来判断是否存在正方形。四个点两两组合，一共会组合出4次，所以最终结果 = 统计结果 / 4。

c++

#include <iostream>
#include <vector>
using namespace std;

// 定义一个点结构体
struct Point {
    int x, y;
};

// 判断两个点是否相等
bool arePointsEqual(Point a, Point b) {
    return a.x == b.x && a.y == b.y;
}

// 检查数组中是否存在某点
bool pointExists(vector<Point>& points, Point p) {
    for (auto& point : points) {
        if (arePointsEqual(point, p)) {
            return true;
        }
    }
    return false;
}

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

    vector<Point> points(n);

    // 读取坐标并存入数组
    for (int i = 0; i < n; i++) {
        cin >> points[i].x >> points[i].y;
    }

    int squareCount = 0;

    // 遍历所有点对，检查是否能构成正方形
    for (int i = 0; i < n; i++) {
        int x1 = points[i].x;
        int y1 = points[i].y;

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

            // 计算两个可能的对角点
            Point p3 = {x1 - (y1 - y2), y1 + (x1 - x2)};
            Point p4 = {x2 - (y1 - y2), y2 + (x1 - x2)};

            if (pointExists(points, p3) && pointExists(points, p4)) {
                squareCount++;
            }

            // 计算另外两个可能的对角点
            Point p5 = {x1 + (y1 - y2), y1 - (x1 - x2)};
            Point p6 = {x2 + (y1 - y2), y2 - (x1 - x2)};

            if (pointExists(points, p5) && pointExists(points, p6)) {
                squareCount++;
            }
        }
    }

    // 每个正方形被计算了4次，因此结果需要除以4
    cout << squareCount / 4 << endl;

    return 0;
}

Java

import java.util.*;

class Point {
    int x, y;

    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    // 判断两个点是否相等
    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Point) {
            Point p = (Point) obj;
            return this.x == p.x && this.y == p.y;
        }
        return false;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        Set<Point> points = new HashSet<>();
        List<Point> pointList = new ArrayList<>();

        // 读取坐标并存入集合和列表
        for (int i = 0; i < n; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            Point p = new Point(x, y);
            points.add(p);
            pointList.add(p);
        }

        int squareCount = 0;

        // 遍历所有点对，检查是否能构成正方形
        for (int i = 0; i < n; i++) {
            Point p1 = pointList.get(i);

            for (int j = i + 1; j < n; j++) {
                Point p2 = pointList.get(j);

                // 计算两个可能的对角点
                Point p3 = new Point(p1.x - (p1.y - p2.y), p1.y + (p1.x - p2.x));
                Point p4 = new Point(p2.x - (p1.y - p2.y), p2.y + (p1.x - p2.x));

                if (points.contains(p3) && points.contains(p4)) {
                    squareCount++;
                }

                // 计算另外两个可能的对角点
                Point p5 = new Point(p1.x + (p1.y - p2.y), p1.y - (p1.x - p2.x));
                Point p6 = new Point(p2.x + (p1.y - p2.y), p2.y - (p1.x - p2.x));

                if (points.contains(p5) && points.contains(p6)) {
                    squareCount++;
                }
            }
        }

        // 每个正方形被计算了4次，因此结果需要除以4
        System.out.println(squareCount / 4);
        scanner.close();
    }
}

Python

import sys

# 读取输入
n = int(sys.stdin.readline().strip())
points = set()
point_list = []

# 读取坐标并存入集合和列表
for _ in range(n):
    x, y = map(int, sys.stdin.readline().strip().split())
    point = (x, y)
    points.add(point)
    point_list.append(point)

square_count = 0

# 遍历所有点对，检查是否能构成正方形
for i in range(n):
    x1, y1 = point_list[i]

    for j in range(i + 1, n):
        x2, y2 = point_list[j]

        # 计算两个可能的对角点
        p3 = (x1 - (y1 - y2), y1 + (x1 - x2))
        p4 = (x2 - (y1 - y2), y2 + (x1 - x2))

        if p3 in points and p4 in points:
            square_count += 1

        # 计算另外两个可能的对角点
        p5 = (x1 + (y1 - y2), y1 - (x1 - x2))
        p6 = (x2 + (y1 - y2), y2 - (x1 - x2))

        if p5 in points and p6 in points:
            square_count += 1

# 每个正方形被计算了4次，因此结果需要除以4
print(square_count // 4)

JavaScript

const readline = require("readline");

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

const points = new Set();
const pointList = [];
let n;
let lineCount = 0;

rl.on("line", (line) => {
    if (lineCount === 0) {
        n = parseInt(line.trim());
    } else {
        const [x, y] = line.trim().split(" ").map(Number);
        const key = `${x},${y}`;
        points.add(key);
        pointList.push([x, y]);
    }

    lineCount++;

    if (lineCount > n) {
        rl.close();
    }
});

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

    // 遍历所有点对，检查是否能构成正方形
    for (let i = 0; i < n; i++) {
        const [x1, y1] = pointList[i];

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

            // 计算两个可能的对角点
            const p3 = `${x1 - (y1 - y2)},${y1 + (x1 - x2)}`;
            const p4 = `${x2 - (y1 - y2)},${y2 + (x1 - x2)}`;

            if (points.has(p3) && points.has(p4)) {
                squareCount++;
            }

            // 计算另外两个可能的对角点
            const p5 = `${x1 + (y1 - y2)},${y1 - (x1 - x2)}`;
            const p6 = `${x2 + (y1 - y2)},${y2 - (x1 - x2)}`;

            if (points.has(p5) && points.has(p6)) {
                squareCount++;
            }
        }
    }

    // 每个正方形被计算了4次，因此结果需要除以4
    console.log(Math.floor(squareCount / 4));
});

Go

package main

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

// 解析输入
func parseInput() ([][2]int, map[[2]int]bool) {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	n, _ := strconv.Atoi(scanner.Text())

	points := make(map[[2]int]bool)
	pointList := make([][2]int, n)

	for i := 0; i < n; i++ {
		scanner.Scan()
		tokens := strings.Fields(scanner.Text())
		x, _ := strconv.Atoi(tokens[0])
		y, _ := strconv.Atoi(tokens[1])

		p := [2]int{x, y}
		points[p] = true
		pointList[i] = p
	}
	return pointList, points
}

func main() {
	pointList, points := parseInput()
	n := len(pointList)
	squareCount := 0

	// 遍历所有点对，检查是否能构成正方形
	for i := 0; i < n; i++ {
		x1, y1 := pointList[i][0], pointList[i][1]

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

			p3 := [2]int{x1 - (y1 - y2), y1 + (x1 - x2)}
			p4 := [2]int{x2 - (y1 - y2), y2 + (x1 - x2)}

			if points[p3] && points[p4] {
				squareCount++
			}

			p5 := [2]int{x1 + (y1 - y2), y1 - (x1 - x2)}
			p6 := [2]int{x2 + (y1 - y2), y2 - (x1 - x2)}

			if points[p5] && points[p6] {
				squareCount++
			}
		}
	}

	fmt.Println(squareCount / 4)
}