MnZn求问简单凸包 WA0 玄关
查看原帖
MnZn求问简单凸包 WA0 玄关
311306
dk_qwq楼主2024/11/13 23:29

RT,我是fw,对着题解都调不出来

#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#include <vector>
#include <algorithm>
#include <iomanip>
#define pb emplace_back
using namespace std;
#define db double
struct CvHull{
    struct Point{
        db x, y;
        bool IsLim;
        Point() = default;
        Point(db x, db y) : x(x), y(y) {}
        Point operator+ (Point b) {return {x + b.x, y + b.y};}
        Point operator- (Point b) {return {x - b.x, y - b.y};}
        db operator* (Point b) {return x * b.x + y * b.y;}
        bool operator< (Point b) const {return x != b.x ? x < b.x : y < b.y;}
    };
    db cross(Point u, Point v) {return u.x * v.y - u.y * v.x;}
    db cross(Point u, Point v, Point w) {return cross(w - v, v - u);}
    db slope(Point u, Point v) {return (u.y - v.y) / (u.x - v.x);}
    db Length(Point u) {return sqrt(u.x * u.x + u.y * u.y);}

    set<Point>p;
    db C;
    const db inf = 1e100;
    const db fni = 1e10;
    void init() {
        p.clear();
        Point L = {-fni,-inf}, R = {fni, -inf};
        L.IsLim = R.IsLim = true;
        p.insert(L), p.insert(R);
    }
    void update(Point u, Point v, int sgn) {
        if(u.IsLim || v.IsLim) return ;
        C += Length(u-v) * sgn;
    }
    void insert(Point u) {
        p.insert(u);
        auto it = p.find(u);
        auto pre = prev(it), nxt = next(it);
        if(cross(*pre, *it, *nxt) <= 0) {
            p.erase(it);return ;
        }
        update(*pre, *nxt, -1);
        update(*pre, *it, 1);
        update(*it, *nxt, 1);
        while(pre != p.begin()) {
            auto pp = prev(pre);
            if (cross(*pp, *pre, *it) <= 0){
                update(*pre, *it, -1);
                update(*pp, *pre, -1);
                update(*pp, *it, 1);
                p.erase(pre);
            } else break;
            pre = pp;
        }
        while(nxt != --p.end()){
            auto qq = next(nxt);
            if (cross(*it, *nxt, *qq) <= 0){
                update(*it, *nxt, -1);
                update(*nxt, *qq, -1);
                update(*it, *qq, 1);
                p.erase(nxt);
            } else break;
            nxt = qq;
        }
    }
} G;

const int N = 2e5+5;
int n, m, q, x, y;
CvHull::Point a[N];
struct Query{
    int opt;// 1 add / 2 query
    int pos;
}Q[N];
vector<db>ans;
bool Del[N];
int main() {
    // freopen("P2521.in", "r", stdin);
    // freopen("P2521.out", "w", stdout);
    ios::sync_with_stdio(false),cin.tie(nullptr);
    cin >> n >> x >> y;
    G.init();
    G.insert({0, 0});
    G.insert({n, 0});
    G.insert({x, y});
    cin >> m;
    for(int i = 1; i <= m; i++) cin >> a[i].x >> a[i].y;
    cin >> q;
    for(int i = 1; i <= q; i++) {
        cin >> Q[i].opt;
        if(Q[i].opt == 1) cin >> Q[i].pos, Del[Q[i].pos] = true;
    }
    for(int i = 1; i <= m; i++)
        if(!Del[i]) G.insert(a[i]);
    for(int i = q; i >= 1; i--) {
        if(Q[i].opt == 2) ans.pb(G.C);
        if(Q[i].opt == 1) G.insert(a[Q[i].pos]);
    }
    reverse(ans.begin(), ans.end());
    for(auto v : ans) cout << setprecision(3) << v << endl;
}
2024/11/13 23:29
加载中...