题解 P2521 【[HAOI2011]防线修建】
rhjoi
2019-08-05 08:26:23
----
SOL
=
题意：离线询问，维护动态凸包，支持加点，查询凸包周长。
用set，按x坐标排序，先判断是否在凸包内，再用双向迭代器向两边枚举删点即可。
具体实现参照代码。
//set很够用了，可能不会再手写平衡树来维护动态凸包了。
//代码有所借鉴某大佬
---
CODE
=
```cpp
#include<bits/stdc++.h>
#define pf printf
#define sf scanf
#define cs const
#define ll long long
#define db double
#define int long long
using namespace std;
cs int N=1e6+10;
cs db eps=1e-7,inf=1e18,pi=acos(-1);
struct Vector {
int x,y;
Vector (int x=0,int y=0):x(x),y(y){}
friend Vector operator +(cs Vector &a,cs Vector &b){return Vector(a.x+b.x,a.y+b.y);}
friend Vector operator -(cs Vector &a,cs Vector &b){return Vector(a.x-b.x,a.y-b.y);}
friend int operator *(cs Vector &a,cs Vector &b){return a.x*b.y-a.y*b.x;}
bool operator <(cs Vector &t)cs{
return x==t.x? y<t.y:x<t.x;
//注意双关键字排序维护凸包
}
}p[N],cp;
set<Vector>S;
db now;
inline db lenth(cs Vector &a){
return sqrt(a.x*a.x+a.y*a.y);
}
inline void insert(cs Vector &x){
set<Vector>:: iterator r=S.lower_bound(x),l=r,t;
--l;
if((*l-x)*(*r-x)<0)return;
now-=lenth(*r-*l);
while(r!=S.end()){
t=r;++r;
if(r==S.end()||(*r-x)*(*t-x)>0)break;
now-=lenth(*r-*t);
S.erase(t);
}
while(l!=S.begin()){
t=l;--l;
if((*l-x)*(*t-x)<0)break;
now-=lenth(*l-*t);
S.erase(t);
}
S.insert(x);
l=r=S.find(x);
--l;++r;
now+=lenth(x-*l)+lenth(x-*r);
}
struct node{
int kd,id;
db ans;
}q[N];
int n,m,Q;
bool vis[N];
signed main(){
sf("%d%d%d",&n,&cp.x,&cp.y);
sf("%d",&m);
for(int i=1;i<=m;++i)sf("%d%d",&p[i].x,&p[i].y);
sf("%d",&Q);
for(int i=1;i<=Q;++i){
sf("%d",&q[i].kd);
if(q[i].kd==1)sf("%d",&q[i].id),vis[q[i].id]=1;
}
S.insert(Vector(0,0));
S.insert(Vector(n,0));
S.insert(cp);
now=lenth(cp)+lenth(Vector(n,0)-cp);
for(int i=1;i<=m;++i)if(!vis[i])insert(p[i]);
for(int i=Q;i>=1;--i){
if(q[i].kd==2)q[i].ans=now;
else insert(p[q[i].id]);
}
for(int i=1;i<=Q;++i)if(q[i].kd==2)pf("%.2lf\n",q[i].ans);
return 0;
}
```