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 <bits/stdc++.h>
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;}
};