题解：P2521 [HAOI2011] 防线修建

· · 题解

题意

给出 n，在第一象限的一个稳定点和 m 个非稳定点（坐标保证 x\in (0,n),y \in (0,+\infin)）。存在删除非稳定点的操作，问这些点和 (0,0),(0,n) 组成的凸包外周不与 x 轴重合的边的长度之和。

解法

由于题目没有强制在线，先考虑离线。

我们发现凸包删点事件非常麻烦的事情，考虑将一直没删的点建立凸包后再倒序加点，这时如果存在同时增删点则做线段树分治。

加点时先考虑所加点是否在凸包外，在凸包里面的不加入。另外加入是注意两边都要判断，如果出现左拐则删除，保证凸包涉及的边按顺时针（从左到右）顺序斜率单减。注意比较时用浮点数不好，建议交叉相乘。

维护时考虑用 stl :: set，这样我们会有总体 \operatorname{O}(m\log m) 的动态加点操作，于是题目解决了。

代码

//c++14 O2,213ms,3.59mb,2.52kb
#include<bits/stdc++.h>
using namespace std;
int n,m,q,tp[200009],id[200009],x,y,a[100009],b[100009];
bool vis[200009];
set<pair<int,int> >p;
double ans,prt[200009];
double dis(int x1,int y1,int x2,int y2){
    return __builtin_sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}
void delnode(set<pair<int,int> > :: iterator x){
    auto y = x,z = x;
    //printf("d %d %d\n",x -> first,x -> second);
    y ++,z --;
    ans -= dis(y -> first,y -> second,x -> first,x -> second);
    ans -= dis(z -> first,z -> second,x -> first,x -> second);
    ans += dis(y -> first,y -> second,z -> first,z -> second);
    p.erase(x);
//  printf("%.2lf\n",ans);
}
void addnode(int x,int y){
    //printf("a %d %d\n",x,y);
    auto fx = p.insert(make_pair(x,y)).first;
    auto fy = fx,z = fx;
    fy ++,z --;
    //printf("%d %d %d %d\n",fy -> first,fy -> second,z -> first,z -> second);
    ans += dis(fy -> first,fy -> second,fx -> first,fx -> second);
    ans += dis(z -> first,z -> second,fx -> first,fx -> second);
    ans -= dis(fy -> first,fy -> second,z -> first,z -> second);
}
void pop(int x,int y){
    auto o = p.lower_bound(make_pair(x,y)),fp = o;
    if(o == p.end())
        return;
    fp ++;
    while(p.end() != fp && (o -> second - y) * (fp -> first - o -> first) <= (o -> first - x) * (fp -> second - o -> second))
        delnode(o),o = fp,fp ++;
    o --;
    fp = o;
    if(o == p.begin())
        return;
        fp --;
    while((y - o -> second) * (o -> first - fp -> first) >= (x - o -> first) * (o -> second - fp -> second)){
        delnode(o);
        o = fp;
        if(o != p.begin())
            fp --;
        else
            break;
    }
}
void ins(int x,int y){
    auto o = p.lower_bound(make_pair(x,y));
    auto fp = o;
    fp --;
    if(o -> first == x)
        return;
    else if(fp -> first == x){
        delnode(fp);
        pop(x,y);
        addnode(x,y);
    }
    else if((o -> second - y) * (x - fp -> first) < (o -> first - x) * (y - fp -> second))
        pop(x,y),addnode(x,y);
}
/*
Author:OtterZ
Tag:offline,slope trick,geometry
*/
int main(){
    scanf("%d %d %d",&n,&x,&y);
    ans = __builtin_sqrt(x * x + y * y) + __builtin_sqrt((n - x) * (n - x) + y * y);
    p.insert(make_pair(0,0)),p.insert(make_pair(n,0)),p.insert(make_pair(x,y));
    scanf("%d",&m);
    for(int i = 1; i <= m; i ++){
        scanf("%d %d",&a[i],&b[i]);
    }
    scanf("%d",&q);
    for(int i = 1; i <= q; i ++){
        scanf("%d",&tp[i]);
        if(tp[i] == 1){
            scanf("%d",&id[i]);
            if(vis[id[i]])
                id[i] = 0;
            vis[id[i]] = true;
        }
    }
    for(int i = 1; i <= m; i ++)
        if(!vis[i])
            ins(a[i],b[i]);
    for(int i = q; i > 0; i --){
        if(id[i] != 0)
            ins(a[id[i]],b[id[i]]);
        else if(tp[i] == 2)
            prt[i] = ans;
        //printf("%.2lf\n",ans);
    }
    for(int i = 1; i <= q; i ++)
        if(tp[i] == 2)
            printf("%.2lf\n",prt[i]);
    return 0;
}