【算法题】构成的正方形数量

共计 1388 个字符，预计需要花费 4 分钟才能阅读完成。

import java.util.Scanner;

/**
 * 标题：构成的正方形数量 | 时间限制：1秒 | 内存限制：262144K | 语言限制：不限
 * 输入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
 * 说明 此4点可构成正方形
 */
public class M_N_T_22 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = Integer.parseInt(scanner.nextLine());

        if (N < 4) {
            System.out.println(0);
            return;
        }

        int[][] zuobiaos = new int[N][2];
        for (int i = 0; i < zuobiaos.length; i++) {
            String[] strings = scanner.nextLine().split(" ");
            zuobiaos[i][0] = Integer.parseInt(strings[0]);
            zuobiaos[i][1] = Integer.parseInt(strings[1]);
        }

        int count = 0;
        for (int i = 0; i < zuobiaos.length - 3; i++) {
            for (int j = i + 1; j < zuobiaos.length - 2; j++) {
                for (int k = j + 1; k < zuobiaos.length - 1; k++) {
                    for (int l = k + 1; l < zuobiaos.length; l++) {
                        if (canBeSquare(zuobiaos[i], zuobiaos[j], zuobiaos[k], zuobiaos[l])) {
                            count++;
                        }
                    }
                }
            }
        }

        System.out.println(count);
    }

    public static boolean canBeSquare(int[] i, int[] j, int[] k, int[] l) {
        return calculate(new int[]{i[0] - j[0], i[1] - j[1]}, new int[]{k[0] - l[0], k[1] - l[1]}) ||
                calculate(new int[]{i[0] - k[0], i[1] - k[1]}, new int[]{j[0] - l[0], j[1] - l[1]}) ||
                calculate(new int[]{i[0] - l[0], i[1] - l[1]}, new int[]{j[0] - k[0], j[1] - k[1]});
    }

    // 关键点： 判断正方形,需要其对角线垂直且长度相等
    public static boolean calculate(int[] vec1, int[] vec2) {
        return vec1[0] * vec2[0] + vec1[1] * vec2[1] == 0 && (vec1[0] * vec1[0] + vec1[1] * vec1[1]) == (vec2[0] * vec2[0] + vec2[1] * vec2[1]);
    }
}