[BZOJ 2300] [HAOI 2011] 防线修建

题意:只有删点与查询操作,动态地维护一个上凸包的周长。

首先可以把题目离线化,倒转时间轴,则可以把题目转换成动态加点并维护凸包周长。

维护的实现可以采用平衡树(set)来做:在树上找到当前点的前驱与后继点(按 xy 坐标排序),然后判断是否符合凸包条件,若不满足则不断删去前驱后继并更新周长。

Note:

  1. 计算初始答案前就应当构建出一个凸包(可以用后面的方法做)。
  2. 这题 cin / cout 非常慢,全改成 scanf / printf 后快了 1s+

Reference:

https://erjiaqing.github.io/2014/04/14/bzoj2300/

代码如下:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<set>
#include<cmath>
#include<iomanip>

using namespace std;

inline void set_file_IO(string);
inline void close_IO(void);
inline void work(void);

int main(void) {
    #ifndef ONLINE_JUDGE
        set_file_IO("defense");
    #endif
    work();
    #ifndef ONLINE_JUDGE
        close_IO();
    #endif
    return 0;
}

const double Eps = 1e-6;

struct Vertex {
    double x, y;
    Vertex() {};
    Vertex(const double _x, const double _y): x(_x), y(_y) {};
    bool operator < (const Vertex b) const {
        return (fabs(x-b.x) < Eps)? y < b.x: x < b.x;
    }
} p[100100];


int op[200100], arg[200100];
double output[200100];
char mrk[100100];

set<Vertex> hull;

double ans = 0;

inline double sqr(const double x) {
    return x * x;
}

inline double dis(const Vertex a, const Vertex b) {
    return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
}

inline double angle_dir(const Vertex a, const Vertex b, const Vertex c) {
    return (b.x - a.x) * (c.y - b.y) - (c.x - b.x) * (b.y - a.y);
}

inline void add(const Vertex v) {
    set<Vertex>::iterator succ = hull.upper_bound(v), pred = succ, ssuc = succ;
    -- pred, ++ ssuc;
    set<Vertex>::iterator ppre = pred;
    -- ppre;
   
    if (angle_dir(v, *pred, *succ) > Eps) {
       
        ans -= dis(*pred, *succ);
       
        while (pred != hull.begin() && angle_dir(*ppre, *pred, v) > Eps) {
            ans -= dis(*ppre, *pred);
            hull.erase(pred);
            pred = ppre --;
        }
        while (ssuc != hull.end() && angle_dir(v, *succ, *ssuc) > Eps) {
            ans -= dis(*ssuc, *succ);
            hull.erase(succ);
            succ = ssuc ++;
        }
       
        hull.insert(v);
        ans += dis(v, *pred) + dis(v, *succ);
    }
}

inline void work(void) {
    double n, x, y;
    int m, q;
    scanf("%lf%lf%lf%d", &n, &x, &y, &m);
    for (int i=1; i<=m; ++i) {
        scanf("%lf%lf", &p[i].x, &p[i].y);
    }
   
    hull.insert(Vertex(0, 0));
    hull.insert(Vertex(n, 0));
    hull.insert(Vertex(x, y));
    ans = dis(Vertex(0, 0), Vertex(x, y)) + dis(Vertex(n, 0), Vertex(x, y));
   
    scanf("%d", &q);
    for (int i=1; i<=q; ++i) {
        scanf("%d", op+i);
        if (op[i] == 1) {
            scanf("%d", arg+i);
            mrk[arg[i]] = true;
        }
    }
   
    for (int i=1; i<=m; ++i) {
        if (!mrk[i]) {
            add(p[i]);
        }
    }
   
    int cnt = 0;
    for (int k=q; k; --k) {
        if (op[k] == 2) {
            output[++cnt] = ans;
        } else {
            add(p[arg[k]]);
        }
    }
   
    for (int i=cnt; i; --i) {
        printf("%.2f\n", output[i]);
    }
}

inline void set_file_IO(string name) {
    freopen((name + ".in" ).c_str(), "r", stdin );
    freopen((name + ".out").c_str(), "w", stdout);
}

inline void close_IO(void) {
    fclose(stdin);
    fclose(stdout);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注