djwj233 的博客

djwj233 的博客

动态凸壳 学习笔记

posted on 2021-11-08 21:23:21 | under 笔记 |

Q & A

和 myee 一起搞的(((

《蓝猫淘气三千问》

动态凸壳有什么用

可以动态地维护凸壳。

为什么要动态维护凸壳

好玩。

为什么动态维护凸壳好玩

可以用于斜率优化。

为什么要斜率优化

因为题目想让我们斜率优化。

为什么题目想让我们斜率优化

因为出题人毒瘤。

为什么出题人毒瘤

因为国民普遍素质不高。

为什么国民普遍素质不高

因为总有人在问为什么。

核心代码

记这个东西主要是因为今天看到了一种短小精悍的写法,借助了 C++ STL multiset(注意 setmultiset 还是有不少区别的,这里用 multiset 更方便)。

以下以维护右上凸壳为例。

点的表示

struct node {
    db x, y;
    node (db X = 0, db Y = 0) : x(X), y(Y) {}
    node operator - (const node &temp) const {
        return node(x-temp.x, y-temp.y);
    }
    db operator ^ (const node &temp) const { // 叉乘
        return x * temp.y - y * temp.x;
    }
    bool operator < (const node &temp) const {
        return x == temp.x ? y > temp.y : x < temp.x ;
    }
} ;

凸壳

struct Convex_Hull {
    multiset<node> S;
    bool valid(multiset<node>::iterator it) {
        auto it2 = next(it);
        if(it == S.begin() || it2 == S.end()) return true;
        auto it1 = prev(it);
        return ((*it - *it1) ^ (*it2 - *it)) > 0.0; // *
    }
    void insert(node t) {
        auto p = S.insert(t);
        if(!valid(p)) {  S.erase(p); return ;  }
        while(p != S.begin() && !valid(prev(p)))
            S.erase(prev(p));
        while(next(p) != S.end() && !valid(next(p)))
            S.erase(next(p));
    }
} H;

我们重点关注打星号的这个过程。

注意到,在右上凸壳中,如果一个点是凸的,那么一定长这样:

所以叉乘为正。

至于给定斜率的询问,我们可以考虑二分对应的 $x$ 坐标,在 multisetlower_bound 处理。

复杂度好像退化成 2log 了?

维护直线

看着就很李超树,但我不会李超树,考虑换种写法。

显然题目想让我们维护一个下凸壳,我们可以把叉积换成交点的 $x$ 坐标。

之后所有的二分都反着来,这题就做完了。

#include<bits/stdc++.h>
using namespace std;
#define fo(v,a,b) for(int v=a;v<=b;v++)
#define fr(v,a,b) for(int v=a;v>=b;v--)
#define cl(a,v) memset(a,v,sizeof(a))

typedef double db;

const db eps = 1e-8, inf = 1e9;
const int N = 100010;

int n;

inline bool eq(db x, db y) {
    return fabs(x - y) <= eps;
}
inline bool leq(db x, db y) {
    return x + eps < y;
}

struct Line {
    db k, b;
    Line(db K, db B) : k(K), b(B) {}
    bool operator<(const Line &temp) const {
        return eq(k, temp.k) ? leq(b, temp.b) : leq(k, temp.k);
    }
    db operator ^ (const Line &temp) const {
        return (temp.b - b) / (k - temp.k);
    }
} ;

struct Convex_Hull
{
    multiset<Line> S;
    bool valid(multiset<Line>::iterator it) {
        auto it2 = next(it);
        if(it2 == S.end()) return true;
        if(it == S.begin()) return leq(it2->b + it2->k, it->b + it->k);
        if(eq(it->k, it2->k)) return leq(it2->b, it->b);
        auto it1 = prev(it);
        if(eq(it->k, it1->k)) return leq(it1->b, it->b);
        return leq((*it1) ^ (*it), (*it) ^ (*it2));
    }
    void insert(Line t) {
        auto p = S.insert(t);
        if(!valid(p)) return S.erase(p), void();
        while(p != S.begin() && !valid(prev(p))) S.erase(prev(p));
        while(next(p) != S.end() && !valid(next(p))) S.erase(next(p));
    }
    db check(db val) {
        auto it = S.lower_bound(Line(val,-inf));
        if(it == S.end()) return inf;
        if(next(it) == S.end()) return inf;
        return (*it) ^ (*next(it));
    }
    db query(int x) {
        db l = 0.0, r = 100.0, mid;
        while(l + 1e-6 < r) {
            mid = (l + r) / 2.0;
            if(leq((db)x, check(mid))) r = mid;
            else l = mid;
        }
        auto it = S.lower_bound(Line(r,-inf));
        return it->k * x + it->b;
    }
} H;

int main()
{
    cin >> n;

    fo(i,1,n) {
        char s[20]; scanf("%s", s+1);
        if(s[1]=='P') {
            db k, b; scanf("%lf%lf", &b, &k), b -= k;
            H.insert(Line(k, b));
        } else {
            int x; scanf("%d", &x);
            printf("%d\n", (int)max(0.0, H.query(x)/100.0) );
        }
    }

    return 0;
}

这么说来,大部分李超树的题都可以用动态凸壳搞。