腾讯2018春招模拟——编程题1——4个点能否构成正方形

题目

判断输入的4个点是否构成正方形
输入t组数据，每组数据包含两行，一行是4个点的横坐标，一行是4个点的纵坐标
示范输入：
2
0 0 1 1
0 1 0 1
0 1 5 6
1 6 0 5
示范输出：
Yes
Yes

我的思路

判断任意3个点是否构成等腰直角三角形，如果是，则为正方形。

public class Main {
    public static void main(String[] args) {
        Scanner in =  new Scanner(System.in);
        int t = in.nextInt();
        String[] result = new String[t];
        int[] x=new int[4];
        int[] y=new int[4];
        for (int i=0;i<t;i++){
            for (int j=0;j<4;j++){
                x[j]=in.nextInt();
            }
            for (int j=0;j<4;j++){
                y[j]=in.nextInt();
            }
            if (isRec(getLength(x[0],y[0],x[1],y[1]),getLength(x[1],y[1],x[2],y[2]),getLength(x[0],y[0],x[2],y[2]))
                && isRec(getLength(x[0],y[0],x[1],y[1]),getLength(x[0],y[0],x[3],y[3]),getLength(x[1],y[1],x[3],y[3]))
                    &&isRec(getLength(x[1],y[1],x[3],y[3]),getLength(x[1],y[1],x[2],y[2]),getLength(x[2],y[2],x[3],y[3]))
                    &&isRec(getLength(x[0],y[0],x[2],y[2]),getLength(x[0],y[0],x[3],y[3]),getLength(x[2],y[2],x[3],y[3]))
            )
                result[i]="Yes";
            else
                result[i]="No";
        }
        for (int i=0;i<result.length;i++)
            System.out.println(result[i]);

    }

    static boolean isRec(int a,int b,int c){
        return a + b == c || a + c == b || b + c == a;
    }
    static int getLength(int x1,int y1,int x2,int y2){
        return (int)(Math.pow(x1-x2,2)+Math.pow(y1-y2,2));
    }

缺点

计算量太大，编程复杂，耗时多，容易出错。

优化思路

这四个点相互之间的距离只有两种，用一个数组用于保存这些点之间的距离，求出两两点之间的距离，若数组不存在所求的距离数值，则添加进数组，若数组超过三个数值，则返回FALSE，最终数组只有2个数值且数值之比为1比根号2，则为TRUE

/**
 * 计算给定的4个点是否可以构成正方形
 */
public class isSquare {
    public static void main(String[] args) {
        Scanner in =  new Scanner(System.in);
        int t = in.nextInt(); 
        String[] result = new String[t]; //存储结果的数组
        int[] x=new int[4];
        int[] y=new int[4];
        List<Integer> list =new  ArrayList<>(); //存储任意两点间的距离（不重复）
        for (int i=0;i<t;i++){
            list.clear();                 //将list情况，避免影响下一轮结果
            for (int j=0;j<4;j++){       //读入x坐标
                x[j]=in.nextInt();
            }
            for (int j=0;j<4;j++){       //读入y坐标
                y[j]=in.nextInt();
            }
            for (int k=0;k<4;k++){     //遍历(0,1)(0,2)(0,3)(1,2)(1,3)(2,3)几个点对
                for (int m=k+1;m<4;m++){
                    int len= getLength(x[k],y[k],x[m],y[m]);//判断并存储两点间的距离
                    if (!list.contains(len))
                        list.add(len);
                }
            }
            if (list.size()==2){
                int a=list.get(0)>list.get(1)? list.get(0)/list.get(1):list.get(1)/list.get(0);
                if (a==2) { //如果距离只有两种，且两调边长度的平方是2倍关系，那么是正方形
                    result[i] = "Yes";
                    continue;
                }
            }
            result[i] = "No";

        }
        for (String aResult : result) System.out.println(aResult);

    }

    /**
     * 计算两个点之间的距离的平方
     * @param x1 点1的横坐标
     * @param y1 点1的纵坐标
     * @param x2 点2的横坐标
     * @param y2 点2的纵坐标
     * @return 两点间距离的平方
     */
    static int getLength(int x1,int y1,int x2,int y2){
        return (int)(Math.pow(x1-x2,2)+Math.pow(y1-y2,2));
    }
}

测试结果

2
0 0 1 1
0 1 0 1
0 1 5 6
1 6 0 5
Yes
Yes