问题#

题目地址：P7529 [USACO21OPEN] Permutation G ↗.

给定 $q$ 次询问，每次询问有两种操作：

向凸包中加入点 $(x,y)$ .
给定直线 $y=kx+b$ ，询问是否与凸包相交。

数据范围： $1\leq q\leq 10^5$ .

凸包与直线的交#

显然，我们首先需要维护上凸包和下凸包。

对直线作两条平行线，分别切于上凸包和下凸包。

如图，找切点可以利用上下凸包的斜率单调性。

形式化地，对于斜率为 $k$ 的直线 $Ax+By=C$ ，我们要在上凸包找到点 $A_i(x_{a_i},y_{a_i})$ 满足 $\operatorname{slope}(\overrightarrow {A_{i-1} A_{i} } ) < k < \operatorname{slope}(\overrightarrow {A_{i}A_{i+1}})$ ，在下凸包中找到点 $B_i(x_{b_i}, y_{b_i})$ 满足 $\operatorname{slope}(\overrightarrow {B_{i-1}B_{i}}) < k < \operatorname{slope}(\overrightarrow {B_{i}B_{i+1}})$ .

之后，将 $(x_{a_i}, y_{a_i})$ 和 $(x_{b_i}, y_{b_i})$ 代入直线方程，得到 $C_a=A\cdot x_{a_i}+B\cdot y_{a_i}$ 和 $C_b=A\cdot x_{b_i}+B\cdot y_{b_i}$ .

若 $C_b\leq C\leq C_a$ 或 $C_a\leq C\leq C_b$ ，说明直线与凸包相交，否则不交。

问题只剩下如何维护凸包。

CDQ 分治优化#

需要动态维护两个凸包，可以平衡树在线处理，但没必要。题目不要求在线，考虑离线下来利用 CDQ 分治优化，更加简单。

对每条直线记录两个变量， $\operatorname{mx}=\max\limits_{i=1}^n(A\cdot x_i + B\cdot y_i)$ ， $\operatorname{mn}=\min\limits_{i=1}^n(A\cdot x_i + B\cdot y_i)$ ，代表把凸包中的每个点代入方程，所得到数值的最大值和最小值。

在此之后，只需判断 $\operatorname{mn} \leq C \leq \operatorname{mx}$ 是否成立即可。

与CDQ分治的大致思想相同，把初始的 $n$ 个点的时间戳设为 $[1,n]$ ，后面的操作从 $n+1$ 开始顺序排列。

设当前在处理区间 $[l,r]$ ，我们用 $[l,mid]$ 中的点来更新 $[mid+1, r]$ 区间中的线，这样以保证时间顺序。

每次分治过程中的更新操作：

构建上凸包，线性，保证斜率按降序排序。
把直线按照斜率降序排序。
CDQ 分治的常规操作，用左半部分更新右半部分中斜率在 $[\operatorname{slope}(\overrightarrow {A_{i-1}A_{i}}), \operatorname{slope}(\overrightarrow {A_{i}A_{i+1}})]$ 范围内的直线所对应的最大纵坐标。
构建下凸包，直线按斜率升序排序，剩余操作与 $3$ 类似，更新纵坐标的最小值。

注意到，过程中利用了斜率单调性。观察发现，当 $Ax+By=C$ 的 $B<0$ ，也就是斜率为负时，会用上凸包更新最小值，下凸包更新最大值，会出现问题。

因此，对于所有 $Ax+By=C,B<0$ ，进行操作 $A\leftarrow -A$ ， $B\leftarrow -B$ ， $C\leftarrow -C$ 即可。

代码实现#

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
	int ret = 0, ch = getchar(), f = 1;
	while(ch < '0' || ch > '9') { if(ch == '-') f = -1, ch = getchar(); }
	while(ch <= '9' && ch >= '0') {
		ret = ret * 10 + ch - '0';
		ch = getchar();
	}
	return ret * f;
}
const int MAXN = 4e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;
int n, Q;
struct Point{
	int opt, x, y, z;
	Point() {}
	Point(int _x, int _y) { x = _x; y = _y; }
	Point(Point a, Point b): x(b.x - a.x), y(b.y - a.y) {} //从A指向B的向量
	friend Point operator + (const Point &a, const Point &b) {
		return Point(a.x + b.x, a.y + b.y);
	}
	friend Point operator - (const Point &a, const Point &b) {
		return Point(a.x - b.x, a.y - b.y);
	}
	friend int operator * (const Point &a, const Point &b) {
		return a.x * b.y - a.y * b.x;
	}
} pt[MAXN], dir[MAXN], ch[MAXN];
typedef Point Vec;
inline bool cmp_p(Point A, Point B) { return A.x < B.x || (A.x == B.x && A.y < B.y); }
struct Query{
	int opt, x, y, z;
} q[MAXN];
struct Line{
	Line() {}
	Line(Point _v, int _id) { v = _v, id = _id; }
	Point v; int id;
} ln[MAXN];

inline bool cmp_l1(Line A, Line B) { return A.v * B.v < 0; }
inline bool cmp_l2(Line A, Line B) { return A.v * B.v > 0; }
int mx[MAXN], mn[MAXN];
inline bool check1(Point s1, Point s2, Point p) {
	return Vec(s2, s1) * Vec(s1, p) >= 0;
}
inline bool check2(Point s1, Point s2, Point p) {
	return Vec(s2, s1) * Vec(s1, p) <= 0;
}
inline void update(int id, int x, int y) {
	mx[id] = max(mx[id], x * q[id].x + y * q[id].y);
	mn[id] = min(mn[id], x * q[id].x + y * q[id].y);
}
void cdq(int l, int r) {
	if(l == r) return ;
	int mid = (l + r) >> 1;
	cdq(l, mid); cdq(mid + 1, r);

	int cntp = 0, cntl = 0;
	for(int i = l; i <= mid; i++) if(q[i].opt == 1) pt[++cntp] = Point(q[i].x, q[i].y);
	for(int i = mid + 1; i <= r; i++) if(q[i].opt == 2) ln[++cntl] = Line(dir[i], i);
	if(cntp == 0 || cntl == 0) return ;
	sort(pt + 1, pt + cntp + 1, cmp_p);
	//找上凸包
	int top = 0;
	ch[++top] = pt[1];
	for(int i = 2; i <= cntp; i++) {
		while(top > 1 && check1(ch[top], ch[top - 1], pt[i]))
			top--;
		ch[++top] = pt[i];
	}
	sort(ln + 1, ln + cntl + 1, cmp_l1);
	int j = 1;
	for(int i = 1; i <= top; i++) {
		while((i == top || ln[j].v * (ch[i + 1] - ch[i]) <= 0) && j <= cntl) {
			update(ln[j].id, ch[i].x, ch[i].y);
			j++;
		}
	}
	//找下凸包
	top = 0;
	ch[++top] = pt[1];
	for(int i = 2; i <= cntp; i++) {
		while(top > 1 && check2(ch[top], ch[top - 1], pt[i]))
			top--;
		ch[++top] = pt[i];
	}
	sort(ln + 1, ln + cntl + 1, cmp_l2);
	j = 1;
	for(int i = 1; i <= top; i++) {
		while((i == top || ln[j].v * (ch[i + 1] - ch[i]) >= 0) && j <= cntl) {
			update(ln[j].id, ch[i].x, ch[i].y);
			j++;
		}
	}
}
signed main() {
	n = read(), Q = read();
	for(int i = 1; i <= n; i++) q[i].x = read(), q[i].y = read(), q[i].opt = 1;
	Q += n;
	for(int i = n + 1; i <= Q; i++) {
		q[i].opt = read();
		if(q[i].opt == 1) q[i].x = read(), q[i].y = read();
		else {
			q[i].x = read(), q[i].y = read(), q[i].z = read();
			if(q[i].y < 0) q[i].x *= -1, q[i].y *= -1, q[i].z *= -1;
			if(q[i].y == 0 && q[i].x < 0) q[i].x *= -1, q[i].z *= -1;
			dir[i] = Point(q[i].y, -q[i].x);
			mx[i] = -inf, mn[i] = inf;
		}
	}
	cdq(1, Q);
	for(int i = n + 1; i <= Q; i++) if(q[i].opt == 2) {
		if(mx[i] - q[i].z < 0 || mn[i] - q[i].z > 0) puts("YES");
		else puts("NO");
	}
	return 0;
}

cpp

【洛谷-P7529】- 动态凸包与 CDQ 分治

问题#

凸包与直线的交#

CDQ 分治优化#

代码实现#