一句話題意：給你一個(gè)凸包，每次可以插入一個(gè)點(diǎn)或者詢問(wèn)周長(zhǎng)。

動(dòng)態(tài)凸包裸題嘛，用\(Set\)實(shí)現(xiàn)。最初每個(gè)點(diǎn)坐標(biāo)做乘三處理，便于取初始三角形的重心作為凸包判定原點(diǎn)。

#include <bits/stdc++.h> using namespace std;const int N = 500000 + 5; const double eps = 1e-8;int n, m, x, y, q, px[N], py[N], ban[N];struct Point {int x, y; double ang; }o;Point operator - (Point lhs, Point rhs) {return (Point) {lhs.x - rhs.x, lhs.y - rhs.y}; }double disPP (Point lhs, Point rhs) {return hypot (abs (lhs.x - rhs.x), abs (lhs.y - rhs.y)); }bool operator < (Point lhs, Point rhs) {if (fabs (lhs.ang - rhs.ang) > eps) {return lhs.ang < rhs.ang;} else {return disPP (lhs, o) < disPP (rhs, o);} }int Cross (Point lhs, Point rhs) {return lhs.x * rhs.y - lhs.y * rhs.x; }struct Query {int opt, x;}qry[N];set <Point> s;typedef set <Point> :: iterator Iter;double cur_ans = 0;stack <double> ans;Iter Prev (Iter it) {return it == s.begin () ? (--s.end ()) : (--it); }Iter Next (Iter it) {return (++it) == s.end () ? s.begin () : it; }void Insert (Point P) {Iter nxt = s.lower_bound (P); if (nxt == s.end ()) {nxt = s.begin ();}Iter pre = Prev (nxt);if (Cross (P - *pre, *nxt - P) <= 0) {return; // 已經(jīng)在凸包里面 }s.insert (P); Iter i, j, cur = s.find (P);i = Prev (cur), j = Prev (i);pre = Prev (cur), nxt = Next (cur);cur_ans += disPP (*cur, *pre);cur_ans += disPP (*cur, *nxt);cur_ans -= disPP (*pre, *nxt);while (Cross (*i - *j, *cur - *i) <= 0) {cur_ans -= disPP (*cur, *i);cur_ans -= disPP (*i, *j);cur_ans += disPP (*cur, *j);s.erase (i); i = j; j = Prev (j);} i = Next (cur), j = Next (i);while (Cross (*i - *cur, *j - *i) <= 0) {cur_ans -= disPP (*cur, *i);cur_ans -= disPP (*i, *j);cur_ans += disPP (*cur, *j);s.erase (i); i = j; j = Next (j);} }int main () { // freopen ("data.in", "r", stdin);cin >> n >> x >> y >> m;x *= 3, y *= 3, n *= 3;for (int i = 1; i <= m; ++i) {cin >> px[i] >> py[i];px[i] *= 3; py[i] *= 3;}cin >> q;for (int i = 1; i <= q; ++i) {cin >> qry[i].opt;if (qry[i].opt == 1) {cin >> qry[i].x;ban[qry[i].x] = true;} }o = (Point) {(n + x) / 3, y / 3, 0};Point P1 = (Point) {0, 0, atan2 (0 - o.y, 0 - o.x)};Point P2 = (Point) {n, 0, atan2 (0 - o.y, n - o.x)};Point P3 = (Point) {x, y, atan2 (y - o.y, x - o.x)};s.insert (P1);s.insert (P2); cur_ans += disPP (P2, P3);s.insert (P3); cur_ans += disPP (P1, P3);for (int i = 1; i <= m; ++i) {if (!ban[i]) {Insert ((Point) {px[i], py[i], atan2 (py[i] - o.y, px[i] - o.x)});}}for (int i = q; i >= 1; --i) {if (qry[i].opt == 1) {int t = qry[i].x;Insert ((Point) {px[t], py[t], atan2 (py[t] - o.y, px[t] - o.x)});} else {ans.push (cur_ans);}}while (!ans.empty ()) {cout << fixed << setprecision (2) << ans.top () / 3.0 << endl;ans.pop ();} }

轉(zhuǎn)載于:https://www.cnblogs.com/maomao9173/p/10931793.html

總結(jié)

以上是生活随笔為你收集整理的【bzoj2300】【Luogu P2521】 [HAOI2011]防线修建 动态凸包，平衡树，Set的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。