算法题：Java编程判断给定坐标数组中可以组成的正方形个数并打印它们的坐标组合

用户3587585

发布于 2023-09-07 10:22:18

2680

发布于 2023-09-07 10:22:18

前言

某次参加华为OD机考，其中抽中的一道题是输入一组坐标集合，然后输出可以组成正方形的个数以及能组成正方形的坐标组合，当时自己也是一筹莫展，竟然用四条相邻的边相等和相邻两条边的夹角为90度这样的数学建模来解决，结果花了很长时间硬是没解出来。现在回过头来继续刷一下这道算法题，发现其实它并不是那么难。下面我把自己对这道算法题的解题思路和代码重新整理了一遍。

题目描述

用例一输入：{{1,1},{1,2},{2,1},{2,2},{1,3}}

输出：

{1,1},{1,2},{2,1},{2,2}

用例二输入：{{1,1}, {1,2}, {2,1}, {2,2}, {1,3}, {3,1}, {3,3}, {2,3}, {3,2}}

输出：

{1,1},{1,2},{2,1},{2,2} {1,1},{1,3},{3,1},{3,3} {1,2},{2,2},{1,3},{2,3} {2,1},{2,2},{3,1},{3,2} {2,2},{3,3},{2,3},{3,2}

解题思路

1、从所有坐标集合中任意选出所有4个坐标的组合；

2、遍历所有4个点坐标组合，根据4个点组成的四边形首先判断两条对角线的中点是否重合，不重合则一定不是正方形；

3、根据点的坐标判断两条邻边是否相等以及两条邻边长度的平方和是否等于对象线长度的平方和；

4、若同时满足条件2和4，则该组四个点组成正方形，正方形计数加1，同时将该坐标组合添加到一个新的List中；

5、遍历结束，输出正方形计数并遍历打印所有能组成正方形的List中的坐标组合。

编码实现

import java.util.*;

public class Pointer {

    int x; // 横坐标
    int y; // 纵坐标

    public Pointer(int x, int y){
        this.x = x;
        this.y = y;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String inputLine = scanner.nextLine().trim();
        // 分割输入字符串
        String[] pointStrArray = inputLine.substring(2, inputLine.length()-2).split("},\\{");
        List<Pointer> pointers = new ArrayList<>();
        for(String pointStr: pointStrArray){
            String[] pointString = pointStr.split(",");
            // 拆分的数组第一个值为横坐标，第二个值为纵坐标
            Pointer pointer = new Pointer(Integer.parseInt(pointString[0]), Integer.parseInt(pointString[1]));
            pointers.add(pointer);
        }
        // 计算出所有4个点的坐标组合 C(4,points.length)
        List<List<Pointer>> fourPointerList = new ArrayList<>();
        for(int i=0;i<pointers.size()-3;i++){
            for(int j=i+1;j<pointers.size()-2;j++){
                for(int m=j+1;m<pointers.size()-1;m++){
                    for(int n=m+1;n<pointers.size();n++){
                        List<Pointer> fourPoints = new ArrayList<>();
                        fourPoints.add(pointers.get(i)); // 第1个坐标
                        fourPoints.add(pointers.get(j)); // 第2个坐标
                        fourPoints.add(pointers.get(m)); // 第3个坐标
                        fourPoints.add(pointers.get(n)); // 第4个坐标
                        fourPointerList.add(fourPoints);
                    }
                }
            }
        }
        int squareCount = 0;
        List<List<Pointer>> resultList = new ArrayList<>();
        for(List<Pointer> fourPoints: fourPointerList){
            if(isSquare(fourPoints)){
                squareCount++;
                resultList.add(fourPoints);
            }
        }
        System.out.println(squareCount);
        for(List<Pointer> fourPoints: resultList){
            StringBuilder builder = new StringBuilder();
     builder.append('{').append(fourPoints.get(0).x).append(',').append(fourPoints.get(0).y).append('}').append(',')
                    .append('{').append(fourPoints.get(1).x).append(',').append(fourPoints.get(1).y).append('}').append(',')
                    .append('{').append(fourPoints.get(2).x).append(',').append(fourPoints.get(2).y).append('}').append(',')
                    .append('{').append(fourPoints.get(3).x).append(',').append(fourPoints.get(3).y).append('}');
            System.out.println(builder);
        }
    }
   
}

// 判断是否是正方形，对角线中心到4个点的距离相等，且相邻两条边与对角线组成直角三角形
    // 横坐标或纵坐标存在相等的两个点不可能组成对角线交点
    public static boolean isSquare(List<Pointer> pointers){
        Pointer pointer0 = pointers.get(0);
        // 对角点
        Pointer againstPointer = null;
        int index = 0;
        for(int i=1;i<4;i++){
            againstPointer = pointers.get(i);
            index = i;
            // 寻找与point1可以组成对角线的点
            if(pointer0.x!=againstPointer.x && pointer0.y!=againstPointer.y){
                break;
            }
        }
        if(againstPointer==null){
            return false; // 后面三个点中不存在与第一点能组成对角线的点时，表示至少有3个点在同一条直线上，必定不能组成正方形
        }
        if(index==1){
            // 正方形中两对相互组成对角线的两个点的横纵坐标值满足相等，不相等则必定不是正方形
            if(!(pointer0.x+againstPointer.x==pointers.get(2).x+pointers.get(3).x
                    && pointer0.y+againstPointer.y==pointers.get(2).y+pointers.get(3).y)){
                return false;
            }else{
                // 两条相邻边长的平方和等于对角线的平方和
                // fourPoints[0]与fourPoints[1]组成对角线，fourPoints[2]与fourPoints[3]组成对角线
                int line1Square = calcLineLength(pointers.get(0), pointers.get(2));
                int line2Square = calcLineLength(pointers.get(0), pointers.get(3));
                int line3Square = calcLineLength(pointers.get(0), pointers.get(1));
                if(line1Square==line2Square && line1Square+line2Square==line3Square){
                    return true;
                }
            }
        }else if(index==2){
            if(!(pointer0.x+againstPointer.x==pointers.get(1).x+pointers.get(3).x
            && pointer0.y+againstPointer.y==pointers.get(1).y+pointers.get(3).y)){
                return false;
            } else {
                int line1Square = calcLineLength(pointers.get(0), pointers.get(1));
                int line2Square = calcLineLength(pointers.get(0), pointers.get(3));
                int line3Square = calcLineLength(pointers.get(0), pointers.get(2));
                if(line1Square==line2Square && line1Square+line2Square==line3Square){
                    return true;
                }
            }
        } else { // index = 3
            if(!(pointer0.x+againstPointer.x==pointers.get(1).x+pointers.get(2).x
            && pointer0.y+againstPointer.y==pointers.get(1).y+pointers.get(2).y)){
                return false;
            } else {
                int line1Square = calcLineLength(pointers.get(0), pointers.get(1));
                int line2Square = calcLineLength(pointers.get(0), pointers.get(2));
                int line3Square = calcLineLength(pointers.get(0), pointers.get(3));
                if(line1Square==line2Square && line1Square+line2Square==line3Square){
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 计算两个坐标连成直线的长度的平方和
     * @param pointA
     * @param pointB
     * @return lineLength
     */
    public static int calcLineLength(Pointer pointA, Pointer pointB){
        int lineLength = (pointB.x-pointA.x)*(pointB.x-pointA.x)+(pointB.y-pointA.y)*(pointB.y-pointA.y);
        return lineLength;
    }
    
}

测试结果

在IDEA中执行Main方法，然后在控制台中输入测试用例一参数：{{1,1},{1,2},{2,1},{2,2},{1,3}} 控制台输出:

1
{1,1},{1,2},{2,1},{2,2}

在IDEA中重新执行Main方法，然后在控制台中输入测试用例二参数：{{1,1},{1,2},{2,1},{2,2},{1,3},{3,1},{3,3},{2,3},{3,2}} 控制台输出:

5
{1,1},{1,2},{2,1},{2,2}
{1,1},{1,3},{3,1},{3,3}
{1,2},{2,2},{1,3},{2,3}
{2,1},{2,2},{3,1},{3,2}
{2,2},{3,3},{2,3},{3,2}

输入的9个坐标中选出4个点一共有C(4,9)共21种组合，从程序的输出结果我们可以看到它们只能组成5个正方形，把他们放到坐标系中验证5组4个点的组合都可以组成正方形。