当前位置：首页 > news >正文

构成正方形的数量

news 2024/10/28 4:09:31

题目描述

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

输入描述

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

之后的 N 行输入为坐标 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点可构成正方形

题解

先求出任意两个点的距离，一共六个距离。

如果这六个距离，没有0并且只有两种距离，那么就是正方形。

源码 Java

import java.util.ArrayList;
import java.util.HashSet;public class Square {static Input input;static  {input = new Input("4\n" +"0 0\n" +"1 2\n" +"3 1\n" +"2 -1");}public static void main(String[] args) {Integer count = Integer.parseInt(input.nextLine());ArrayList<Point> points = new ArrayList<>();for (int i = 0; i < count; i++) {points.add(new Point(input.nextLine().split(" ")));}int counter = 0;for (int i = 0; i < count; i++) {for (int j = i + 1; j < count; j++) {for (int k = j + 1; k < count; k++) {for (int m = k + 1; m < count; m++) {if (isSquare(points.get(i), points.get(j), points.get(k), points.get(m))) {counter++;}}}}}System.out.println(counter);}public static boolean isSquare(Point p1, Point p2, Point p3, Point p4) {Point[] points = {p1, p2, p3, p4};int d1 = distance(p1, p2);int d2 = distance(p2, p3);int d3 = distance(p3, p4);int d4 = distance(p4, p1);int d5 = distance(p1, p3);int d6 = distance(p2, p4);HashSet<Integer> set = new HashSet<>();set.add(d1);set.add(d2);set.add(d3);set.add(d4);set.add(d5);set.add(d6);return set.size() == 2 && d1>0 && d2 > 0 && d3 > 0 && d4 > 0 && d5 > 0 && d6 > 0;}public static int distance(Point p1, Point p2) {int x = p1.x - p2.x;int y = p1.y - p2.y;return x*x + y*y;}static class Point {public int x;public int y;public Point(String[] xy) {this.x = Integer.parseInt(xy[0]);this.y = Integer.parseInt(xy[1]);}}
}