• 向凸包中加入点 $(x,y)$.
  • 给定直线 $y=kx+b$,询问是否与凸包相交。
  • 数据范围:$1\leq q\leq 10^5$. ">
  • 向凸包中加入点 $(x,y)$.
  • 给定直线 $y=kx+b$,询问是否与凸包相交。
  • 数据范围:$1\leq q\leq 10^5$. "> P7529 - 动态凸包与CDQ分治 - 学习笔记 - TonyYin - Blog
    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
    小恐龙
    花!
    上一篇
    下一篇