8-26 阿里模拟试题附加题多边题问题

/**
 * @author jerryzhuo
 * @since 2019/8/26
 */

import java.util.*;
import java.util.List;

public class Main {
/** 请完成下面这个函数，实现题目要求的功能 **/
    /**
     * 当然，你也可以不按照这个模板来作答，完全按照自己的想法来
     **/
    public static String measureDistance(List<Double> xList, List<Double> yList, double x, double y) {
        //点是否在多边形内的标志位，false->在，true->不在
        boolean ifIn = false;
        //多边形顶点数量
        int count = xList.size();

        //判断点是否在多边形内,有多种方法，这里使用了比较简洁的一种，直接看是比较难看懂的，所以建议搜百度上，上面有更加详细的解释
        for (int i = 0, j = count - 1; i < count; j = i++) {
            boolean judge =
                    ((yList.get(i) > y) != (yList.get(j) > y))
                            && (x < (xList.get(j) - xList.get(i)) * (y - yList.get(i)) / (yList.get(j) - yList.get(i)) + xList.get(i));
            if (judge) {
                ifIn = !ifIn;
            }
        }

        if (ifIn) {
            //点在多边形内,直接返回
            return "yes,0";
        } else {
            //点不在多边形内,所以要计算距离,distance表示距离(这个变量的声明在后面)

            //先找到距离点最近的那一条边
            double min1 = Double.MAX_VALUE;
            double min2 = Double.MAX_VALUE;
            int pointerAIndex = -1;
            int pointerBIndex = -1;
            for (int i = 0; i < count; i++) {
                double x0 = xList.get(i);
                double y0 = yList.get(i);

                double temp = Math.pow(x0 - x, 2) + Math.pow(y0 - y, 2);
                if (temp <= min1) {
                    pointerBIndex = pointerAIndex;
                    pointerAIndex = i;
                    min2 = min1;
                    min1 = temp;
                } else if (temp <= min2) {
                    min2 = temp;
                    pointerBIndex = i;
                }
            }

            //两个点（ax,ay),(bx,by)
            double ax = xList.get(pointerAIndex);
            double ay = yList.get(pointerAIndex);
            double bx = xList.get(pointerBIndex);
            double by = yList.get(pointerBIndex);

            //点斜式求直线要考虑斜率不存在的情况,这里做了点变化，第一个if是斜率不存在的情况，第二个是ay = by的时候，所以直接算结果就好了，不用使用最后一个
            double distance;
            if (ax == bx) {
                distance = Math.abs(x - ax);
            } else if ((ay == by)) {
                distance = Math.abs(y - ay);
            } else {
                double k = (ay - by) / (ax - bx);
                double b = ay - k * ax;
                distance = (Math.abs(y - k * x - b) / Math.sqrt(1 + k * k));
            }

            //"no," + 四舍五入的值
            return "no," + Math.round(distance);
        }
    }


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String line = in.nextLine();
        //(x,y)为小广所在的位置
        double x = Double.parseDouble(line.split(",")[0]);
        double y = Double.parseDouble(line.split(",")[1]);

        line = in.nextLine();
        //xList记录了多边形n个点的x坐标,yList记录了多边形n个点的y坐标
        List<Double> xList = new ArrayList<>();
        List<Double> yList = new ArrayList<>();
        String[] array = line.split(",");
        for (int i = 0; i < array.length; i++) {
            xList.add(Double.parseDouble(array[i]));
            yList.add(Double.parseDouble(array[i + 1]));
            i++;
        }
        in.close();
        System.out.println(measureDistance(xList, yList, x, y));
    }
}