liansha.java

package JZ_Offer;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

/**
 * Created by liuwentao on 2020-10-25 13:22
 */
public class Main {
    public static void main(String[] args) throws Exception{
        // 创建一个BufferedReader对象
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 读取第一行数据
        String line = br.readLine();

//        // 第一行数字
        int peopleNum = Integer.parseInt(line);
        ArrayList<int[]> data = new ArrayList<>();
        for (int i = 0; i < peopleNum; i++) {
            // 读取第二行数据
            line = br.readLine();
            String[] temp = line.trim().split(" ");
            int x = Integer.valueOf(temp[0]);
            int y = Integer.valueOf(temp[1]);
            data.add(new int[]{x, y});
        }
        // 进行暴力
//        int peopleNum = 6;
//        ArrayList<int[]> data = new ArrayList<>();
//        data.add(new int[]{1, 0});
//        data.add(new int[]{2, 1});
//        data.add(new int[]{3, 2});
//        data.add(new int[]{4, 3});
//        data.add(new int[]{5, 0});
//        data.add(new int[]{6, 19});

        // 如果所有点都相等情况
        int z = 0;
        for (; z < data.size() - 1; z++) {
            if (data.get(z)[0] != data.get(z+1)[0] || data.get(z)[1] != data.get(z+1)[1]) {
                break;
            }
        }
        if (z == data.size() - 1) {
            System.out.println(data.size());
            return;
        }

        System.out.println(new Main().help(data));

    }

    // 这个函数可以返回穿过把data中没有visited的点都穿过 所花的最小线条
    public int help(ArrayList<int[]> data) {
        // 边界
        if (0 == data.size()) {
            return 0;
        }
        if (0 == data.size() - 1) {
            return 1;
        }
        if (0 == data.size() - 2) {
            return 1;
        }
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < data.size() - 1; i++) {
            ArrayList<Integer> mylist = new ArrayList<>();
            for (int j = i + 1; j < data.size(); j++) {
                if (mylist.contains(j)) {
//                    System.out.println("continue啦" + i+ "：" + j);
                    continue;
                }

                // i, j都没访问过,我就拿i,j组成一条线，然后再把其它节点看看在不在这条线上

                int[] point1 = data.get(i);
                int[] point2 = data.get(j);
                if (point1[0] == point2[0] && point1[1] == point2[1]) {
                    continue;
                }

                ArrayList<int[]> tempList = new ArrayList<>();
                for (int x = 0; x < data.size(); x++) {
                    if (x != i && x != j) {
                        // 看一下data.get(x)在不在线上
                        if (!test(point1[0], point1[1], point2[0], point2[1], data.get(x)[0], data.get(x)[1])) {
//                            System.out.println("加入templist：" + x);
                            tempList.add(data.get(x)); // data.get(x)不在线上就放到tempList中
                        } else {
//                            System.out.println("加入mylist：" + x);
                            mylist.add(x);
                        }
                    }

                }

                int tempMax = help(tempList);
                result = Math.min(result, tempMax + 1);
            }
        }
        return result;
    }

    private boolean test(int x1, int y1, int x2, int y2, int x, int y) {
        int g1 = gcd(y2 - y1, x2 - x1);
        if(y == y2 && x == x2){
            return true;
        }
        int g2 = gcd(y - y2, x - x2);
        return (y2 - y1) / g1 == (y - y2) / g2 && (x2 - x1) / g1 == (x - x2) / g2;
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }
}