P7529 – 动态凸包与CDQ分治

问题

题目地址:P7529 [USACO21OPEN] Permutation G.

给定 $q$ 次询问,每次询问有两种操作:

  1. 向凸包中加入点 $(x,y)$.
  2. 给定直线 $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}})

之后,将 $(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]$ 区间中的线,这样以保证时间顺序。

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

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

 

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇