---

前言

       简单记录一下笔试情况。

一、判断一点是否在三角形中

题目简介

       输入四个二维坐标，前三个点表示一个三角形，判断最后一个点是否在其内（不包含恰好在边上的情况）。

一、面积

       海伦公式：p=(a+b+c)/2，S=sqrt(p*(p-a)*(p-b)*(p-c));
       假设三角形三个点为A，B，C，若O点位于三角形内，则有：S(ABC)=S(ABO)+S(ACO)+S(BCO)。并且任意一个小三角形面积不为0，例如：S(ABO)=0，表示 O 点落于AB边上。

代码实现

      

import java.math.BigDecimal;
public class Solution {
    public boolean judge (double[] point1, double[] point2, double[] point3, double[] point) {
        double S=getArea(point1,point2,point3);
        double S1=getArea(point1,point2,point),
                S2=getArea(point1,point3,point),
                S3=getArea(point2,point3,point);
//        if(S1==0.0||S2==0.0||S3==0.0||Math.abs(S-S1-S2-S3)<1e-6)// 误差精度：0.000001;
//            return false;
//        return true;

        //或者采用 BigDecimal
        BigDecimal s1=BigDecimal.valueOf(S1),
                s2=BigDecimal.valueOf(S2),
                s3=BigDecimal.valueOf(S3);
        BigDecimal s=BigDecimal.valueOf(S);
        BigDecimal a=new BigDecimal("0.0");
        if(s1.compareTo(a)==0||s2.compareTo(a)==0||s3.compareTo(a)==0||s.compareTo(s1.add(s2).add(s3))!=0)
            return false;
        return true;
    }
    private double getArea(double[] a,double[] b,double[] c){
        double ab=Math.sqrt(Math.pow(b[1]-a[1],2)+Math.pow(b[0]-a[0],2));
        double ac=Math.sqrt(Math.pow(c[1]-a[1],2)+Math.pow(c[0]-a[0],2));
        double bc=Math.sqrt(Math.pow(b[1]-c[1],2)+Math.pow(b[0]-c[0],2));
        double p=(ab+bc+ac)/2;
        return Math.sqrt(p*(p-ab)*(p-ac)*(p-bc));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

二、向量

       由于double数比较时存在精度损失，对于某些情况可能会产生错误的结果。

       二维坐标系中：A(x1,y1) 和 B(x2,y2) 构成的向量 AB（A指向B）：(x2-x1,y2-y1);

       AB(x1,y1)， BC(x2,y2) ：
       向量点乘：AB · AC=|AB|*|AC|*cosθ = x1*y1+x2*y2; 若 AB // AC，则点乘结果和|AB|*|AC|相等。

       向量叉乘：AB x AC = (x1*y2，x2*y1); 叉乘生成一个第三维的向量，其大小为 |AB|*|AC|*sinθ，方向通过右手法则来判定：(x1*y2-x2*y1的值为正，其方向指向z轴正方向；为负指向z轴负方向（可以采用向量 (1，1) 分别与 (1，0) (0，1) 尝试验证）；为零时，两向量平行。
https://zhuanlan.zhihu.com/p/359975221
https://zhuanlan.zhihu.com/p/356529702

代码实现

public class Solution {
    public boolean judge (double[] point1, double[] point2, double[] point3, double[] point) {
        // 将三个点 逆时针 排列，
        if(getDirect(point1,point2,point3))// 1,2,3 逆时针排列。
            return getDirect(point1,point2,point)&&getDirect(point2,point3,point)
                    &&getDirect(point3,point1,point);
        else   //顺序为 1,3,2
            return getDirect(point1,point3,point)&&getDirect(point3,point2,point)
                    &&getDirect(point2,point1,point);
    }
    private boolean getDirect(double[] a,double[] b,double[] c){ // 点 c 是否在 ab向量的左侧，即叉乘结果大于0
        double x1=b[0]-a[0],y1=b[1]-a[1];
        double x2=c[0]-a[0],y2=c[1]-a[1];
        return x1*y2-y1*x2>0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二、求矩阵中的最小步数

题目简介

       二维数组中 n*m，值为0或者1，0表示可以通过，1表示不能通过。求从(0,0)处走到(n-1,m-1)处所需要的最小步数（一次只能走一步）

       题目保证可以从 （0，0）可以走到（n-1,m-1）。

代码实现

import java.util.*;
public class Solution {
    /**
     * @param map int整型二维数组
     * @return int整型
     */
    public int floodFill(int[][] map, int n, int m) {
        // write code here
        Deque<int[]> q=new ArrayDeque<>();
        int[] x={1,-1,0,0},y={0,0,1,-1};
        int step=0;
        q.offer(new int[]{0,0,0});
        map[0][0]=1;
        int res=Integer.MAX_VALUE;
        while(!q.isEmpty()){
            int t=q.size();
            step++;
            int newX,newY;
            while(t--!=0){
                int[] tmp=q.poll();
                if(tmp[0]==n-1&&tmp[1]==m-1)
                    return tmp[2];

                for(int i=0;i<4;i++){
                    newX=tmp[0]+x[i];
                    newY=tmp[1]+y[i];
                    if(newX>=0&&newX<n&&newY>=0&&newY<m&&map[newX][newY]==0){
                        q.offer(new int[]{newX,newY,step});
                        map[newX][newY]=1;
                    }
                }
            }

        }
        return 0;
    }
    public static void main(String[] args) {
        int[][] a=new int[][]{
                {0,0,0,0},
                {0,0,0,0},
                {0,0,0,0},
                {0,0,0,0}
        };
        Solution s=new Solution();
        int res=s.floodFill(a,4,4);
        System.out.println(res);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

总结

完