点点关系

问题描述

点点关系处理平面上两点之间的基本关系，包括距离计算、向量运算等。常用于最近点对、凸包等问题。

基本操作

算法思想

使用坐标表示点的位置
基于向量进行计算
适用于距离和方向判断
时间复杂度 $\mathcal{O}(1)$

代码实现

c++
java
python

class Point {
public:
    double x, y;
    
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    
    // 向量加法
    Point operator + (const Point& p) const {
        return Point(x + p.x, y + p.y);
    }
    
    // 向量减法
    Point operator - (const Point& p) const {
        return Point(x - p.x, y - p.y);
    }
    
    // 点积
    double dot(const Point& p) const {
        return x * p.x + y * p.y;
    }
    
    // 叉积
    double cross(const Point& p) const {
        return x * p.y - y * p.x;
    }
    
    // 欧氏距离
    double distance(const Point& p) const {
        return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
    }
    
    // 曼哈顿距离
    double manhattanDistance(const Point& p) const {
        return abs(x - p.x) + abs(y - p.y);
    }
};

class Point {
    double x, y;
    
    Point(double x, double y) {
        this.x = x;
        this.y = y;
    }
    
    // 向量加法
    Point add(Point p) {
        return new Point(x + p.x, y + p.y);
    }
    
    // 向量减法
    Point subtract(Point p) {
        return new Point(x - p.x, y - p.y);
    }
    
    // 点积
    double dot(Point p) {
        return x * p.x + y * p.y;
    }
    
    // 叉积
    double cross(Point p) {
        return x * p.y - y * p.x;
    }
    
    // 欧氏距离
    double distance(Point p) {
        return Math.sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
    }
    
    // 曼哈顿距离
    double manhattanDistance(Point p) {
        return Math.abs(x - p.x) + Math.abs(y - p.y);
    }
}

class Point:
    def __init__(self, x: float = 0, y: float = 0):
        self.x = x
        self.y = y
    
    # 向量加法
    def __add__(self, p: 'Point') -> 'Point':
        return Point(self.x + p.x, self.y + p.y)
    
    # 向量减法
    def __sub__(self, p: 'Point') -> 'Point':
        return Point(self.x - p.x, self.y - p.y)
    
    # 点积
    def dot(self, p: 'Point') -> float:
        return self.x * p.x + self.y * p.y
    
    # 叉积
    def cross(self, p: 'Point') -> float:
        return self.x * p.y - self.y * p.x
    
    # 欧氏距离
    def distance(self, p: 'Point') -> float:
        return ((self.x - p.x) ** 2 + (self.y - p.y) ** 2) ** 0.5
    
    # 曼哈顿距离
    def manhattan_distance(self, p: 'Point') -> float:
        return abs(self.x - p.x) + abs(self.y - p.y)

时间复杂度分析

操作时间复杂度空间复杂度

向量运算	$\mathcal{O}(1)$	$\mathcal{O}(1)$
点积叉积	$\mathcal{O}(1)$	$\mathcal{O}(1)$
距离计算	$\mathcal{O}(1)$	$\mathcal{O}(1)$
方向判断	$\mathcal{O}(1)$	$\mathcal{O}(1)$

应用场景

距离计算
向量运算
方向判断
凸包构建
最近点对

注意事项

浮点数精度
除零判断
特殊情况
坐标范围
数值稳定性

常见变形

最近点对

cpp
java
python

class Solution {
public:
    // 分治法求最近点对
    double closestPair(vector<Point>& points) {
        sort(points.begin(), points.end(), 
             [](const Point& a, const Point& b) {
                 return a.x < b.x;
             });
        return closest(points, 0, points.size() - 1);
    }
    
private:
    double closest(vector<Point>& points, int left, int right) {
        if (right - left <= 3) {
            return bruteForce(points, left, right);
        }
        
        int mid = (left + right) / 2;
        double midX = points[mid].x;
        double d1 = closest(points, left, mid);
        double d2 = closest(points, mid + 1, right);
        double d = min(d1, d2);
        
        vector<Point> strip;
        for (int i = left; i <= right; i++) {
            if (abs(points[i].x - midX) < d) {
                strip.push_back(points[i]);
            }
        }
        
        return min(d, stripClosest(strip, d));
    }
    
    double stripClosest(vector<Point>& strip, double d) {
        sort(strip.begin(), strip.end(),
             [](const Point& a, const Point& b) {
                 return a.y < b.y;
             });
        
        double minDist = d;
        for (int i = 0; i < strip.size(); i++) {
            for (int j = i + 1; j < strip.size() && 
                 strip[j].y - strip[i].y < minDist; j++) {
                minDist = min(minDist, strip[i].distance(strip[j]));
            }
        }
        return minDist;
    }
    
    double bruteForce(vector<Point>& points, int left, int right) {
        double minDist = DBL_MAX;
        for (int i = left; i < right; i++) {
            for (int j = i + 1; j <= right; j++) {
                minDist = min(minDist, points[i].distance(points[j]));
            }
        }
        return minDist;
    }
};

class Solution {
    // 分治法求最近点对
    public double closestPair(Point[] points) {
        Arrays.sort(points, (a, b) -> Double.compare(a.x, b.x));
        return closest(points, 0, points.length - 1);
    }
    
    private double closest(Point[] points, int left, int right) {
        if (right - left <= 3) {
            return bruteForce(points, left, right);
        }
        
        int mid = (left + right) / 2;
        double midX = points[mid].x;
        double d1 = closest(points, left, mid);
        double d2 = closest(points, mid + 1, right);
        double d = Math.min(d1, d2);
        
        List<Point> strip = new ArrayList<>();
        for (int i = left; i <= right; i++) {
            if (Math.abs(points[i].x - midX) < d) {
                strip.add(points[i]);
            }
        }
        
        return Math.min(d, stripClosest(strip, d));
    }
    
    private double stripClosest(List<Point> strip, double d) {
        strip.sort((a, b) -> Double.compare(a.y, b.y));
        double minDist = d;
        
        for (int i = 0; i < strip.size(); i++) {
            for (int j = i + 1; j < strip.size() && 
                 strip.get(j).y - strip.get(i).y < minDist; j++) {
                minDist = Math.min(minDist, 
                    strip.get(i).distance(strip.get(j)));
            }
        }
        return minDist;
    }
    
    private double bruteForce(Point[] points, int left, int right) {
        double minDist = Double.MAX_VALUE;
        for (int i = left; i < right; i++) {
            for (int j = i + 1; j <= right; j++) {
                minDist = Math.min(minDist, points[i].distance(points[j]));
            }
        }
        return minDist;
    }
}

class Solution:
    # 分治法求最近点对
    def closest_pair(self, points: List[Point]) -> float:
        points.sort(key=lambda p: p.x)
        return self.closest(points, 0, len(points) - 1)
    
    def closest(self, points: List[Point], left: int, right: int) -> float:
        if right - left <= 3:
            return self.brute_force(points, left, right)
        
        mid = (left + right) // 2
        mid_x = points[mid].x
        d1 = self.closest(points, left, mid)
        d2 = self.closest(points, mid + 1, right)
        d = min(d1, d2)
        
        strip = []
        for i in range(left, right + 1):
            if abs(points[i].x - mid_x) < d:
                strip.append(points[i])
        
        return min(d, self.strip_closest(strip, d))
    
    def strip_closest(self, strip: List[Point], d: float) -> float:
        strip.sort(key=lambda p: p.y)
        min_dist = d
        
        for i in range(len(strip)):
            j = i + 1
            while j < len(strip) and strip[j].y - strip[i].y < min_dist:
                min_dist = min(min_dist, strip[i].distance(strip[j]))
                j += 1
        return min_dist
    
    def brute_force(self, points: List[Point], left: int, right: int) -> float:
        min_dist = float('inf')
        for i in range(left, right):
            for j in range(i + 1, right + 1):
                min_dist = min(min_dist, points[i].distance(points[j]))
        return min_dist

凸包构建

cpp
java
python

class Solution {
public:
    // Graham扫描法求凸包
    vector<Point> grahamScan(vector<Point>& points) {
        if (points.size() <= 3) return points;
        
        // 找到最下方的点
        int bottom = 0;
        for (int i = 1; i < points.size(); i++) {
            if (points[i].y < points[bottom].y ||
                (points[i].y == points[bottom].y && 
                 points[i].x < points[bottom].x)) {
                bottom = i;
            }
        }
        swap(points[0], points[bottom]);
        
        // 按极角排序
        Point p0 = points[0];
        sort(points.begin() + 1, points.end(),
             [&p0](const Point& a, const Point& b) {
                 double cross = (a - p0).cross(b - p0);
                 if (cross == 0) {
                     return p0.distance(a) < p0.distance(b);
                 }
                 return cross > 0;
             });
        
        // Graham扫描
        vector<Point> hull;
        hull.push_back(points[0]);
        hull.push_back(points[1]);
        
        for (int i = 2; i < points.size(); i++) {
            while (hull.size() >= 2 && 
                   (hull.back() - hull[hull.size() - 2])
                   .cross(points[i] - hull.back()) <= 0) {
                hull.pop_back();
            }
            hull.push_back(points[i]);
        }
        
        return hull;
    }
};

class Solution {
    // Graham扫描法求凸包
    public List<Point> grahamScan(Point[] points) {
        if (points.length <= 3) {
            return Arrays.asList(points);
        }
        
        // 找到最下方的点
        int bottom = 0;
        for (int i = 1; i < points.length; i++) {
            if (points[i].y < points[bottom].y ||
                (points[i].y == points[bottom].y && 
                 points[i].x < points[bottom].x)) {
                bottom = i;
            }
        }
        Point temp = points[0];
        points[0] = points[bottom];
        points[bottom] = temp;
        
        // 按极角排序
        final Point p0 = points[0];
        Arrays.sort(points, 1, points.length,
            (a, b) -> {
                double cross = a.subtract(p0).cross(b.subtract(p0));
                if (cross == 0) {
                    return Double.compare(p0.distance(a), p0.distance(b));
                }
                return cross > 0 ? -1 : 1;
            });
        
        // Graham扫描
        List<Point> hull = new ArrayList<>();
        hull.add(points[0]);
        hull.add(points[1]);
        
        for (int i = 2; i < points.length; i++) {
            while (hull.size() >= 2 && 
                   hull.get(hull.size()-1).subtract(
                       hull.get(hull.size()-2))
                   .cross(points[i].subtract(
                       hull.get(hull.size()-1))) <= 0) {
                hull.remove(hull.size()-1);
            }
            hull.add(points[i]);
        }
        
        return hull;
    }
}

class Solution:
    # Graham扫描法求凸包
    def graham_scan(self, points: List[Point]) -> List[Point]:
        if len(points) <= 3:
            return points
        
        # 找到最下方的点
        bottom = min(range(len(points)), 
                    key=lambda i: (points[i].y, points[i].x))
        points[0], points[bottom] = points[bottom], points[0]
        
        # 按极角排序
        p0 = points[0]
        points[1:] = sorted(
            points[1:],
            key=lambda p: (
                -(p - p0).cross(Point(1, 0)),
                p0.distance(p)
            )
        )
        
        # Graham扫描
        hull = [points[0], points[1]]
        
        for i in range(2, len(points)):
            while len(hull) >= 2 and \
                  (hull[-1] - hull[-2]).cross(points[i] - hull[-1]) <= 0:
                hull.pop()
            hull.append(points[i])
        
        return hull

牛客代码笔记-牛栋文章被收录于专栏

汗牛充栋，学海无涯。<br/> 内含算法知识点讲解，以及牛客题库精选例题。<br/> 学习算法，从牛栋开始。