洛谷 P2521 [HAOI2011]防线修建(动态凸包)

Description:

近来A国和B国的矛盾激化，为了预防不测，A国准备修建一条长长的防线，当然修建防线的话，肯定要把需要保护的城市修在防线内部了。可是A国上层现在还犹豫不决，到底该把哪些城市作为保护对象呢？又由于A国的经费有限，所以希望你能帮忙完成如下的一个任务：

给出你所有的A国城市坐标
A国上层经过讨论，考虑到经济问题，决定取消对i城市的保护，也就是说i城市不需要在防线内了
A国上层询问对于剩下要保护的城市，修建防线的总经费最少是多少

你需要对每次询问作出回答。注意单位1长度的防线花费为1。

A国的地形是这样的，形如下图，x轴是一条河流，相当于一条天然防线，不需要你再修建

A国总是有两个城市在河边，一个点是(0,0)，一个点是(n,0)，其余所有点的横坐标均大于0小于n，纵坐标均大于0。A国有一个不在(0,0)和(n,0)的首都。(0,0),(n,0)和首都这三个城市是一定需要保护的。

Input:

第一行，三个整数n,x,y分别表示河边城市和首都是(0,0)，(n,0)，(x,y)。

第二行，一个整数m。

接下来m行，每行两个整数a,b表示A国的一个非首都非河边城市的坐标为(a,b)。

再接下来一个整数q，表示修改和询问总数。

接下来q行每行要么形如1 i，要么形如2，分别表示撤销第i个城市的保护和询问。

30%的数据m<=1000,q<=1000

100%的数据m<=100000,q<=200000,n>1

所有点的坐标范围均在10000以内, 数据保证没有重点

Output:

对于每个询问输出1行，一个实数v，表示修建防线的花费，保留两位小数

Sample Input:

4 2 1
2
1 2
3 2
5
2
1 1
2
1 2
2

Sample Output:

6.47
5.84
4.47

题目链接

将所有询问反转并离线处理城市的删除操作就可以变为动态凸包的插入操作，考虑用平衡树维护凸包点集（其实用 $s e t$ 也可以进行简单的实现），这样问题就变得和 CodeForces 70D Professor’s task(动态凸包) 十分类似，只是多了周长的维护操作

询问反转后先将必须保护的三个点加入凸包点集中，将这三个点的重心作为基准点利用极角排序进行维护（注意全程没有删除过的城市要利用插入操作提前加入到凸包点集中）

考虑向凸包点集中插入一个点（若点在凸包内部则无需插入）

有凸包点集 $s = {A, B, C, D, E}$ ，现将点 $F$ 加入到 $s$ 中考虑周长变化

首先将线段 $A B$ 删除并添加线段 $A F 、 B F$ ，之后在删除 $A 、 B$ 点时将与其相连的两条线段删除并将两远端顶点相连

这样凸包周长的变化规律就很明显了

AC代码:

#include <bits/stdc++.h>
using namespace std;

typedef double db;
const int maxn = 1e5 + 5;
const db eps = 1e-9;

int Sgn(db Key) {return fabs(Key) < eps ? 0 : (Key < 0 ? -1 : 1);}
int Cmp(db Key1, db Key2) {return Sgn(Key1 - Key2);};
struct Point {db X, Y;};
typedef Point Vector;
Vector operator - (Vector Key1, Vector Key2) {return (Vector){Key1.X - Key2.X, Key1.Y - Key2.Y};}
Vector operator + (Vector Key1, Vector Key2) {return (Vector){Key1.X + Key2.X, Key1.Y + Key2.Y};}
db operator * (Vector Key1, Vector Key2) {return Key1.X * Key2.X + Key1.Y * Key2.Y;}
db operator ^ (Vector Key1, Vector Key2) {return Key1.X * Key2.Y - Key1.Y * Key2.X;}
db GetLen(Vector Key) {return sqrt(Key * Key);}
db DisPointToPoint(Point Key1, Point Key2) {return sqrt((Key2 - Key1) * (Key2 - Key1));}

int N;
db X, Y;
Point Basic;
int M;
set<Point> S;
Point City[maxn];
bool Vis[maxn];
int Q;
vector<pair<int, int>> Query;
vector<db> Ans;
db Len;
int Op, K;

bool operator < (Point Key1, Point Key2) {
    Key1 = Key1 - Basic; Key2 = Key2 - Basic;
    db Ang1 = atan2(Key1.Y, Key1.X), Ang2 = atan2(Key2.Y, Key2.X);
    db Len1 = GetLen(Key1), Len2 = GetLen(Key2);
    if (Cmp(Ang1, Ang2) != 0) return Cmp(Ang1, Ang2) < 0;
    return Cmp(Len1, Len2) < 0;
}

set<Point>::iterator Prev(set<Point>::iterator Key) {
    if (Key == S.begin()) Key = S.end();
    return --Key;
}

set<Point>::iterator Next(set<Point>::iterator Key) {
    ++Key;
    return Key == S.end() ? S.begin() : Key;
}

bool Check(Point Key) {
    set<Point>::iterator it = S.lower_bound(Key);
    if (it == S.end()) it = S.begin();
    return Sgn((Key) - *(Prev(it)) ^ (*(it) - *(Prev(it)))) <= 0;
}

void Insert(Point Key) {
    if (Check(Key)) return;
    S.insert(Key);
    Len -= DisPointToPoint(*(Next(S.find(Key))), *(Prev(S.find(Key))));
    Len += DisPointToPoint(*(S.find(Key)), *(Next(S.find(Key)))) + DisPointToPoint(*(S.find(Key)), *(Prev(S.find(Key))));
    set<Point>::iterator Cur = Next(S.find(Key));
    while (S.size() > 3 && Sgn((Key - *(Next(Cur)) ^ (*(Cur) - *(Next(Cur))))) <= 0) {
        Len -= DisPointToPoint(*(Cur), *(Next(Cur))) + DisPointToPoint(*(Cur), *(Prev(Cur)));
        Len += DisPointToPoint(*(Next(Cur)), *(Prev(Cur)));
        S.erase(Cur);
        Cur = Next(S.find(Key));
    }
    Cur = Prev(S.find(Key));
    while (S.size() > 3 && Sgn((Key - *(Cur)) ^ (*(Cur) - *(Prev(Cur)))) >= 0) {
        Len -= DisPointToPoint(*(Cur), *(Next(Cur))) + DisPointToPoint(*(Cur), *(Prev(Cur)));
        Len += DisPointToPoint(*(Next(Cur)), *(Prev(Cur)));
        S.erase(Cur);
        Cur = Prev(S.find(Key));
    }
}

int main(int argc, char *argv[]) {
    scanf("%d%lf%lf", &N, &X, &Y);
    Basic.X = ((db)N + X) / 3.0; Basic.Y = Y / 3.0;
    S.insert((Point){0.0, 0.0}); S.insert((Point){(db)N, 0.0}); S.insert((Point){X, Y});
    Len = GetLen((Vector){X, Y}) + DisPointToPoint((Point){(db)N, 0.0}, (Point){X, Y});
    scanf("%d", &M);
    for (int i = 1; i <= M; ++i) scanf("%lf%lf", &City[i].X, &City[i].Y);
    scanf("%d", &Q);
    for (int i = 1; i <= Q; ++i) {
        scanf("%d", &Op);
        if (Op == 1) {
            scanf("%d", &K);
            Query.push_back(make_pair(Op, K));
            Vis[K] = true;
        }
        Query.push_back(make_pair(Op, 0));
    }
    for (int i = 1; i <= M; ++i)
        if (!Vis[i])
            Insert(City[i]);
    reverse(Query.begin(), Query.end());
    for (auto &q : Query) {
        if (q.first == 1) Insert(City[q.second]);
        else if (q.first == 2) Ans.push_back(Len);
    }
    reverse(Ans.begin(), Ans.end());
    for (auto &it : Ans) printf("%.2lf\n", it);
    return 0;
}