面试题 16.03. 交点

Tags: Hard Math

Links: https://leetcode-cn.com/problems/intersection-lcci/

---

给定两条线段（表示为起点start = {X1, Y1}和终点end = {X2, Y2}），如果它们有交点，请计算其交点，没有交点则返回空值。

要求浮点型误差不超过10^-6。若有多个交点（线段重叠）则返回 X 值最小的点，X 坐标相同则返回 Y 值最小的点。

示例 1：

输入：
line1 = {0, 0}, {1, 0}
line2 = {1, 1}, {0, -1}
输出： {0.5, 0}

示例 2：

输入：
line1 = {0, 0}, {3, 3}
line2 = {1, 1}, {2, 2}
输出： {1, 1}

示例 3：

输入：
line1 = {0, 0}, {1, 1}
line2 = {1, 0}, {2, 1}
输出： {}，两条线段没有交点

提示：

• 坐标绝对值不会超过 2^7
• 输入的坐标均是有效的二维坐标

---

#include <cmath>
class Solution {
    struct Point {
        double x, y;
        Point(double x = 0, double y = 0): x(x), y(y) {}

        Point operator+(Point p) { return Point(x + p.x, y + p.y); }
        Point operator-(Point p) { return Point(x - p.x, y - p.y); }
        Point operator*(double k) { return Point(x * k, y * k); }
        Point operator/(double k) { return Point(x / k, y / k); }

        double abs() { return sqrt(norm()); }
        double norm() { return x * x + y * y; }

        bool operator<(const Point p) const { return x != p.x ? x < p.x : y < p.y; }

        bool operator==(const Point p) const 
        { return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS; }
    };
    typedef Point Vector;

    struct Segment {
        Point p1, p2;  
    };

    constexpr static double EPS = 1e-6;
    inline bool equals(double a, double b) { return fabs(a - b) < EPS; } 
public:
    double cross(const Vector & a, const Vector & b)
    { return a.x * b.y - a.y * b.x; }

    double dot(const Vector & a, const Vector & b)
    { return a.x * b.x + a.y * b.y; }

    int ccw(Point & p0, Point & p1, Point & p2)
    {
        Vector a = p1 - p0;
        Vector b = p2 - p0;
        if (cross(a, b) > EPS) return -1;
        else if (cross(a, b) < -EPS) return 1;
        else {
            if (dot(a, b) < -EPS) return 2;
            else if (a.norm() < b.norm()) return -2;
            else return 0;
        }
    }

    bool intersection(Point & p1, Point & p2, Point & p3, Point & p4)
    {
        return ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 
            && ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0;
    }

    Point getCrossPoint(Segment s1, Segment s2)
    {
        Vector base = s2.p2 - s2.p1;
        double d1 = abs(cross(base, s1.p1 - s2.p1));
        double d2 = abs(cross(base, s1.p2 - s2.p1));
        if (d1 < EPS && d2 < EPS) {
            Point tmp1 = ccw(s1.p1, s1.p2, s2.p1) == 0 ? s2.p1 : s2.p2;
            Point tmp2 = ccw(s2.p1, s2.p2, s1.p1) == 0 ? s1.p1 : s1.p2;
            return tmp1 < tmp2 ? tmp1 : tmp2;
        }

        double t = d1 / (d1 + d2);
        return s1.p1 + (s1.p2 - s1.p1) * t;
    }

    vector<double> intersection(vector<int>& start1, vector<int>& end1, vector<int>& start2, vector<int>& end2) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        Point p1(start1[0], start1[1]), p2(end1[0], end1[1]), p3(start2[0], start2[1]), p4(end2[0], end2[1]);
        if (!intersection(p1, p2, p3, p4)) return {};

        Segment s1, s2;
        s1.p1 = p1; s1.p2 = p2;
        s2.p1 = p3; s2.p2 = p4;
        Point res = getCrossPoint(s1, s2);

        return vector<double>{res.x, res.y};
    }
};

线段相交的模板题。额外注意线段有部分重合的情况需要特判。