LeeCode AutoX-4 计算几何

题意

传送门 LeeCode AutoX-4 蚂蚁爬行

题解

枚举每一对几何图形，判断相交性，用并查集维护连通性即可。总时间复杂度 $O(n^2+m)$，其中 $n$ 为几何图形数量，$m$ 为查询数量。

根据几何图形性质分类讨论。

判断两圆相交，令 $d$ 表示圆心距离，$r1,r2(r1\le r2)$ 分别为两圆半径，则充要条件为 $r2-r1\le d\le r1+r2$。

判断两线段相交，一类思路是计算出交点，在判断交点是否处于两条线段上；由于只用判断相交性，不用求交点，可以使用基于ccw函数的做法简单求解，具体而言，用端点表示的两条非平行的线段 $(p1,p2),(q1,q2)$，对其中任意线段 $(p1,p2)$ 而言，另一条线段 $(q1,q2)$ 的两个端点必然在 $(p1,p2)$ 所在直线的两侧（或者至多一个端点位于直线上），此时可以通过叉积简单地进行判断。

判断线段与圆的相交性，若圆心到线段所在直线的最小距离大于半径，则不可能相交；反之，若线段存在位于圆上的端点，则相交；若线段存在位于圆内部的端点，则除了两个端点都位于圆内的情况，其他情况都相交；其余情况，圆心与线段两端点的连线都位于圆心与线段的垂线两侧，此时可以通过内积简单地进行判断。

#include 
using namespace std;
using ll = long long;
using lll = __int128;
struct Point {
    ll x, y;
    Point operator+(Point o) {
        return {x + o.x, y + o.y};
    }
    Point operator-(Point o) {
        return {x - o.x, y - o.y};
    }
    ll dot(Point o) {
        return x * o.x + y * o.y;
    }
    ll det(Point o) {
        return x * o.y - o.x * y;
    }
};
struct DSU {
    vector<int> par;
    DSU(int n) : par(n) {
        iota(par.begin(), par.end(), 0);
    }
    int find(int x) {
        return par[x] == x ? x : (par[x] = find(par[x]));
    }
    void unite(int x, int y) {
        x = find(x), y = find(y);
        par[x] = y;
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
};
class Solution {
   public:
    vector<bool> antPass(vector<vector<int>> &geometry, vector<vector<int>> &path) {
        int n = geometry.size();
        DSU dsu(n);
        auto on_seg = [&](Point &p, Point &q1, Point &q2) {
            return (q1 - p).det(q2 - p) == 0 && (q1 - p).dot(q2 - p) <= 0;
        };
        auto intersection = [&](Point &p1, Point &p2, Point &q1, Point &q2) {
            auto f = [&](Point &p1, Point &p2, Point &q1, Point &q2) {
                return (lll)(p1 - p2).det(q1 - p2) * (p1 - p2).det(q2 - p2) <= 0;
            };
            if ((p1 - p2).det(q1 - q2) == 0) {
                return on_seg(p1, q1, q2) || on_seg(p2, q1, q2) || on_seg(q1, p1, p2) || on_seg(q2, p1, p2);
            }
            return f(p1, p2, q1, q2) && f(q1, q2, p1, p2);
        };
        auto in_circle = [&](Point p, Point q, ll r) {
            return (p - q).dot(p - q) < r * r;
        };
        auto on_circle = [&](Point p, Point q, ll r) {
            return (p - q).dot(p - q) == r * r;
        };

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                int n = geometry[i].size(), m = geometry[j].size();
                if (n == m) {
                    if (n == 3) {
                        ll dx = geometry[i][0] - geometry[j][0];
                        ll dy = geometry[i][1] - geometry[j][1];
                        ll r = geometry[i][2] + geometry[j][2];
                        ll l = max(geometry[i][2], geometry[j][2]) - min(geometry[i][2], geometry[j][2]);
                        if (dx * dx + dy * dy <= r * r && dx * dx + dy * dy >= l * l) {
                            dsu.unite(i, j);
                        }
                    } else {
                        Point p1 = {geometry[i][0], geometry[i][1]};
                        Point p2 = {geometry[i][2], geometry[i][3]};
                        Point q1 = {geometry[j][0], geometry[j][1]};
                        Point q2 = {geometry[j][2], geometry[j][3]};
                        if (intersection(p1, p2, q1, q2)) {
                            dsu.unite(i, j);
                        }
                    }
                } else {
                    auto a = geometry[i], b = geometry[j];
                    if (a.size() == 3) {
                        swap(a, b);
                    }
                    Point p1 = {a[0], a[1]};
                    Point p2 = {a[2], a[3]};
                    Point q = {b[0], b[1]};
                    ll r = b[2];
                    lll d = (p1 - p2).det(p1 - q);
                    if (d * d <= (lll)(p1 - p2).dot(p1 - p2) * r * r) {
                        int can = 0;
                        if (on_circle(p1, q, r) || on_circle(p2, q, r)) {
                            can = 1;
                        } else if (in_circle(p1, q, r) || in_circle(p2, q, r)) {
                            can = !(in_circle(p1, q, r) && in_circle(p2, q, r));
                        } else if (((p1 - q).dot(p1 - p2) > 0) != ((p2 - q).dot(p1 - p2) > 0)) {
                            can = 1;
                        }
                        if (can) {
                            dsu.unite(i, j);
                        }
                    }
                }
            }
        }
        int m = path.size();
        vector<bool> res(m);
        for (int i = 0; i < m; ++i) {
            res[i] = dsu.same(path[i][0], path[i][1]);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114