BZOJ【2300】防线修建

描述

在第一象限中给出m个点,其中一共有3个点一定要保护,求最小凸包周长。

在这题中,河道相等于一条防线,于是题目就简化成了求最小上凸包。再看看数据,每次减掉一个要保护的点。我们可以从后往前看,先把没有被询问到的点做一次凸包,接着就可以把删除的点看做是加上去的点。比如把2 3 1 4点依次删除询问,可以看做刚开始一个点都没有,接着把4 1 3 2点依次加入。

所以我们只要先存心每次询问,从后往前做动态凸包即可。

至于动态凸包,由于有三个点一定要保护,于是对于每个新加入的点,找出与其相邻的点, 用叉积判断其是否最优,若不是,就可以将其两边的点删除,继续判断。

在这里,找于加入的点相邻的点可以用平衡树来维护,每次需要O(logn)的时间查找。

可以用自带的set来实现。

关于set,可以看这http://blog.csdn.net/sunshinewave/article/details/8068326


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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<set>
#include<cmath>

using namespace std;

const int N = 100010;

struct node
{
    int x, y;
    friend bool operator <(node a, node b)
    {
        if (a.x == b.x) return a.y < b.y;
        return a.x < b.x;
    }
    friend bool operator ==(node a, node b)
    {
        return a.x == b.x && a.y == b.y;
    }
    friend bool operator !=(node a, node b)
    {
        return a.x != b.x || a.y != b.y;
    }
}p[N], End;

struct Point
{
    int x, y;
    friend bool operator <(Point a, Point b)
    {
        if (a.x == b.x) return a.y > b.y;
        return a.x > b.x;
    }
    friend bool operator ==(Point a, Point b)
    {
        return a.x == b.x && a.y == b.y;
    }
    friend bool operator !=(Point a, Point b)
    {
        return a.x != b.x || a.y != b.y;
    }
}Begin;

set<node> s;
set<Point> se;

double ans[N], Ans;
int n, ques[2 * N], num[N];

node Put(int a, int b)
{
    node x;
    x.x = a, x.y = b;
    return x;
}

double dir(node a, node b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int cj(node a, node b, node c)
{
    return (b.x - a.x) * (c.y - b.y) - (c.x - b.x) * (b.y - a.y)>0?0:1;
}

Point change(node x)
{
    Point t;
    t.x = x.x;
    t.y = x.y;
    return t;
}

node unchange(Point x)
{
    node t;
    t.x = x.x;
    t.y = x.y;
    return t;
}

void Input(node x)
{
    s.insert(x);
    se.insert(change(x));
}

void Delete(node x)
{
    set<node>::iterator a;
    set<Point>::iterator b;
    a = s.find(x);
    b = se.find(change(x));
    s.erase(*a);
    se.erase(*b);
}

void work(node IN)
{
    set<node>::iterator next = s.upper_bound(IN), t;
    set<Point>::iterator last = se.upper_bound((change(IN)));
    if (!cj(unchange(*last), IN, *next)) return ;
    Ans -= dir(unchange(*last), *next);
    node T = *next;
    while (*next != End && !cj(IN, *next, *s.upper_bound((*next))))
    {
        Ans -= dir(*next, *s.upper_bound(*next));
        T = *next;
        next = s.upper_bound((*next));
        Delete(T);
    }
    Point P = *last;
    while (*last != Begin && !cj(unchange(*se.upper_bound(*last)), unchange(*last), IN))
    {
        Ans -= dir(unchange(*last), unchange(*se.upper_bound(*last)));
        P = *last;
        last = se.upper_bound(*last);
        Delete(unchange(P));
    }
    T = *next;
    P = *last;
    Ans += dir(IN, *next) + dir(IN, unchange(*last));
    Input(IN);
}

int main(void)
{
    freopen("defense.in","r",stdin);
    freopen("defense.out","w",stdout);
   
    int x, y, m, q;
    cin >> n >> x >> y;
    Input(Put(0, 0));
    Input(Put(n, 0));
    Input(Put(x, y));
    Begin = change(Put(0, 0));
    End = Put(n, 0);
    Ans = dir(Put(0, 0), Put(x, y)) + dir(Put(n, 0), Put(x, y));
    cin >> m;
    for (int i = 1;i <= m; i++)
    {
       scanf("%d%d", &x, &y);
       p[i] = Put(x, y);
    }
    cin >> q;
    for (int i = 1;i <= q; i++)
    {
       scanf("%d", &x);
       if (x == 1)
           scanf("%d", &ques[i]);
       num[ques[i]] = 1;
    }
    for (int i = 1;i <= m; i++)
       if (!num[i]) work(p[i]);
    for (int i = q;i >= 1; i--)
    {
       if (!ques[i]) ans[i] = Ans;
       else work(p[ques[i]]);
    }
    for (int i = 1;i <= q; i++)
       if (!ques[i]) printf("%.2f\n", ans[i]);
   
    fclose(stdin);
        fclose(stdout);
    return 0;
}

发表评论

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