07 - 点集中找最近点对 - 暴力法

1. 算法思路

两两求距离，找最短距离的两个点

时间复杂度 ：$O(n^2)$

2. 示例代码

2.1 import

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

import primitives.Point;

2.2 暴力法

public static ArrayList<Point> Naive(ArrayList<Point> points) {
    Point p0 = points.get(0);
    Point p1 = points.get(1);
    
    for (int i = 0; i < points.size() - 1; i++) {
        for (int j = i + 1; j < points.size(); j++) {
            if(dist(points.get(i), points.get(j)) < dist(p0, p1)) {
                p0 = points.get(i);
                p1 = points.get(j);
            }
        } 
    }
    
    ArrayList<Point> resultPair = new ArrayList<Point>();
    resultPair.add(p0);
    resultPair.add(p1);
    
    return resultPair;
}

2.3 其他方法

2.3.1 求距离

public static double dist(Point p0, Point p1) {
    return Math.sqrt((p1.getX() - p0.getX()) * (p1.getX() - p0.getX()) +
                        (p1.getY() - p0.getY()) * (p1.getY() - p0.getY()));
}