腾讯暑假实习在线笔编程试模拟试题-正方形判断

╰半橙微兮° 2022-05-29 13:08 210阅读 0赞

> 2018年3月23日牛客网举行了腾讯实习在线模拟笔试

# 先看题目：正方形判断 #

![这里写图片描述][70]  
![这里写图片描述][70 1]

*  **思路1:**  
    用4个点,任意三点组成一个等边直角三角形,并且斜边是直角边的根号2倍(设斜边为y,那么和直角边为x 那么可以推出 y=(√2)\*x ).  
    ![这里写图片描述][70 2]

原理:正方形你可以看着是由两个三角形拼接而成.正方形任意三点组合成等边直接三角形.

> 这个比较简单我就不列出代码了.可以利用数学向量的思想

*    
    
 *  **思路2:**  
    四个点组成6个线段,四个线段长度相等(正方形边长相等),另外两个线段相同(正方形对角线垂直平分且长度相等),***并且你还需要证明 两个的线段长度 是四个线段的长度 根号2倍.***  
    为什么还需要证明长度有根号2倍?.因为有可能是如下情况  
    ![这里写图片描述][70 3]  
    ![这里写图片描述][70 4]

> 图片来自我的金同学

import java.awt.Point;
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.HashMap;
    import java.util.HashSet;
    import java.util.Map;
    import java.util.Scanner;
    
    
    
    public class Main {
        
    
        //向量类 有些方法并没有用到
        static  class MVector{
    
            Point startPoint;
    
            Point endPoint;
    
            Point vector;
    
            int unSqrtDistance;
            int x;
            int y;
    
            public MVector() {
    
            }
    
            public int getY() {
                return y;
            }
    
            public void setY(int y) {
                this.y = y;
                vector=new Point(x, y);
                unSqrtDistance=x*x+y*y;
            }
    
            public MVector(Point startPoint, Point endPoint) {
                super();
    
                this.startPoint = startPoint;
    
                this.endPoint = endPoint;
    
                vector=new Point(endPoint.x-startPoint.x, endPoint.y-startPoint.y);
    
                x=vector.x;
                y=vector.y;
    
                unSqrtDistance=(int) ( Math.pow(endPoint.x-startPoint.x, 2)+Math.pow(endPoint.y-startPoint.y, 2)) ;
            }
    
            public static int mutiply(MVector p1,MVector p2){
    
                int result=p1.x*p2.x+p1.y*p2.y;
    
                return result;
            }
    
            //向量乘法
            public int mutiply(MVector p1){
    
                return mutiply(p1,this);
            }
    
            //两个向量角度
            public static double getAngle(MVector p1,MVector p2){
    
                double resultCos=p1.mutiply(p2)/Math.sqrt((p1.unSqrtDistance*p2.unSqrtDistance));
    
                return Math.acos(resultCos);
    
            }
            public  double getAngle(MVector p2){
    
    
                return getAngle(this,p2);
            }
            public MVector(int x, int y) {
                super();
                this.x = x;
                setY(y);
    
            }
    
    
        }
    
        public static void main(String[] args) {
    
    
            Scanner scanner = new Scanner(System.in);
    
            int n = scanner.nextInt();
            boolean reulst[]= new boolean[n];
    
            int[]points=new int[4];
            MVector[] mVectors= new MVector[6];
            Point point[] = new Point[4];
    
            int flagDistance= Integer.MIN_VALUE;
    
            boolean[]  result=new boolean[n];
    
    
            for (int i = 0; i < n*2; i++) {
    
                for (int j = 0; j < 4; j++) {
    
                    if((i&1)!=0){
                        point[j]=new Point(points[j], scanner.nextInt());
                    }else{
                        points[j]=scanner.nextInt();
                    }
                }
    
                //如果是输入y
                if((i&1)!=0){
    
                    //1-2   第一个点和第二个点组成向量
                    mVectors[0] =new MVector(point[0],point[1]);
    
                    //1-3
                    mVectors[1] =new MVector(point[0],point[2]);
    
                    //1-4
                    mVectors[2] =new MVector(point[0],point[3]);
    
                    //2-3
                    mVectors[3] =new MVector(point[1],point[2]);
    
                    //2-4
                    mVectors[4] =new MVector(point[1],point[3]);
    
                    //3-4
                    mVectors[5] =new MVector(point[2],point[3]);
    
                    //第一个长度
                    int distance1=-1;
                    //长度出现的次数
                    int flag1=0;
                    //同上
                    int distance2=-1;
                    int flag2=0;
                    //注意向量长度为0的问题,如果两个点相同.
                    if (mVectors[0].unSqrtDistance>0) {
                        distance1=mVectors[0].unSqrtDistance;
                        flag1++;
                    }
    
    
    
                    //判断6个边 是否只有两种长度 并且数量是4,另一个是2
                    for (int j = 1; j < mVectors.length&&distance1!=-1; j++) {
                        if(mVectors[j].unSqrtDistance<=0){
                            break;  
                        }
                        else if(distance2==-1&&mVectors[j].unSqrtDistance!=distance1){
                            distance2=mVectors[j].unSqrtDistance;
                            flag2++;
                        }else if(mVectors[j].unSqrtDistance==distance1){
                            flag1++;
                        }else if (mVectors[j].unSqrtDistance==distance2) {
                            flag2++;
                        }else{
                            //出现第三个长度
                            break;
                        }
                    }
    
    
                    if ((flag1==4&&flag2==2)||(flag2==4&&flag1==2)) {
                        //长度根号倍 判断.正方形的边和对角线的平分 差两倍,不要轻易算根号 不然丢精度 如根号5
                        if (distance1<<1==distance2||distance2<<1==distance1) {
                            result[(i-1)/2]=true;
                        }
    
                    }
                }
    
    
            }
    
            System.out.println(Arrays.toString(result));
    
        }
    }

[70]: /images/20220529/dd6241f512cc4ff28b10ed08eaa5fcbe.png
[70 1]: /images/20220529/48f20158a78745a0a53171eb72c9494f.png
[70 2]: /images/20220529/4d29203133ff44f09be1ca597aec61b5.png
[70 3]: /images/20220529/05700492bd14427295550d69ff714e36.png
[70 4]: /images/20220529/c3c60dbdf3564a10bffeda90d43c261c.png