动态凸壳 学习笔记

## Q & A 和 myee 一起搞的（（（ > ## 《蓝猫淘气三千问》 > > #### 动态凸壳有什么用 > > 可以动态地维护凸壳。 > > #### 为什么要动态维护凸壳 > > 好玩。 > > #### 为什么动态维护凸壳好玩 > > 可以用于斜率优化。 > > #### 为什么要斜率优化 > > 因为题目想让我们斜率优化。 > > #### 为什么题目想让我们斜率优化 > > 因为出题人毒瘤。 > > #### 为什么出题人毒瘤 > > 因为国民普遍素质不高。 > > #### 为什么国民普遍素质不高 > > 因为总有人在问为什么。 ## 核心代码 记这个东西主要是因为今天看到了一种短小精悍的写法，借助了 `C++ STL multiset`（注意 `set` 和 `multiset` 还是有不少区别的，这里用 `multiset` 更方便）。 以下以维护右上凸壳为例。 ### 点的表示 ```c++ 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 ; } } ; ``` ### 凸壳 ```c++ 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$ 坐标，在 `multiset` 中 `lower_bound` 处理。 ~~复杂度好像退化成 2log 了？~~ ### 维护直线 - [P4254 [JSOI2008]Blue Mary开公司](https://www.luogu.com.cn/problem/P4254) 看着就很李超树，但我不会李超树，考虑换种写法。 显然题目想让我们维护一个下凸壳，我们可以把叉积换成交点的 $x$ 坐标。 之后所有的二分都反着来，这题就做完了。 ```c++ #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; } ``` 这么说来，大部分李超树的题都可以用动态凸壳搞。