倒过来处理所有询问，就变成了一道动态凸包的裸题
吐槽一下这道题只要维护上凸壳就好了，我zz了没好好看题打了两个2333
// luogu-judger-enable-o2
#include<set>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rp (*r)
#define lp (*l)
#define rrp (*rr)
#define llp (*ll)
using namespace std;
const int maxn=1e6+100;
struct Vector{
double x,y;
Vector(double xx=0,double yy=0){
x=xx,y=yy;
}
};
struct Point{
double x,y;
Point(double xx=0,double yy=0){
x=xx,y=yy;
}
bool operator < (Point a) const{
return x==a.x?y<a.y:x<a.x;
}
}a[maxn],b[maxn],tmp[maxn];
int dcmp(double x){return fabs(x)<1e-9?0:x>0;}
bool operator == (Point a,Point b){return a.x==b.x&&a.y==b.y;}
Vector operator - (Point a,Point b){return Vector(a.x-b.x,a.y-b.y);}
double operator * (Vector a,Vector b){return a.x*b.y-a.y*b.x;}
double dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
double len(Vector a){return sqrt(dot(a,a));}
int m,s,t,ms[maxn],err[maxn],c[maxn],n;
double pp,x,y,ans,an[maxn];
set<Point>u,d;
void tb(Point *p,int &n){
if(n==1) return;
sort(p+1,p+n+1);
tmp[1]=p[1];
int m=1;
for(int i=2;i<=n;i++){
while(m>1&&(tmp[m]-tmp[m-1])*(p[i]-tmp[m-1])<=0)
m--;
tmp[++m]=p[i];
}
for(int i=1;i<m;i++)
d.insert(tmp[i]),ans+=len(tmp[i+1]-tmp[i]);
d.insert(tmp[m]);
int k=m;
for(int i=n-1;i>=1;i--){
while(m>k&&(tmp[m]-tmp[m-1])*(p[i]-tmp[m-1])<=0)
m--;
tmp[++m]=p[i];
}
for(int i=k;i<m;i++)
u.insert(tmp[i]),ans+=len(tmp[i+1]-tmp[i]);
u.insert(tmp[m]);
ans-=pp;
}
void uinsert(Point p){
set<Point>::iterator l,r,ll,rr;
r=u.lower_bound(p);
l=--r,r++;
// printf("%lf %lf\n%lf %lf\n",lp.x,lp.y,rp.x,rp.y);
if((p-lp)*(rp-lp)>0) return;
ans=ans-len(rp-lp)+len(p-lp)+len(p-rp);
while(l!=u.begin()){
ll=--l,l++;
// printf("%lf %lf\n",llp.x,llp.y);
if((lp-llp)*(p-llp)<0) break;
// printf("%lf %lf %lf\n",len(p-lp),len(lp-llp),len(p-llp));
ans=ans-len(p-lp)-len(lp-llp)+len(p-llp);
u.erase(l);
l=ll;
}
rr=++r,r--;
while(rr!=u.end()){
// printf("%lf %lf\n",rrp.x,rrp.y);
if((rrp-p)*(rp-p)>0) break;
// printf("%lf %lf %lf\n",len(rp-p),len(rrp-rp),len(rrp-p));
ans=ans-len(rp-p)-len(rrp-rp)+len(rrp-p);
u.erase(r);
r=rr;
rr=++r,r--;
}
u.insert(p);
}
/*
void dinsert(Point p){
set<Point>::iterator l,r,ll,rr;
r=d.lower_bound(p);
l=--r,r++;
if((p-lp)*(rp-lp)<0) return;
ans=ans-len(rp-lp)+len(p-lp)+len(p-rp);
while(l!=d.begin()){
ll=--l,l++;
if((lp-llp)*(p-llp)>0) break;
ans=ans-len(lp-p)-len(llp-lp)+len(llp-p);
u.erase(l);
l=ll;
}
rr=++r,r--;
while(rr!=d.end()){
if((rrp-p)*(rp-p)>0) break;
ans=ans-len(rp-p)-len(rrp-rp)+len(rrp-p);
u.erase(r);
r=rr;
rr=++r,r--;
}
d.insert(p);
}
*/
int main(){
scanf("%lf%lf%lf",&pp,&x,&y);
scanf("%d",&m);
for(int i=1;i<=m;i++)
scanf("%lf%lf",&b[i].x,&b[i].y);
scanf("%d",&t);
for(int i=1;i<=t;i++){
scanf("%d",&ms[i]);
if(ms[i]==1){
scanf("%d",&c[i]);
err[c[i]]=1;
}
}
a[1].x=a[1].y=a[2].y=0;
a[2].x=pp,a[3].x=x,a[3].y=y;
n=3;
for(int i=1;i<=m;i++)
if(!err[i])
a[++n]=b[i];
tb(a,n);
for(int i=t;i>=1;i--){
if(ms[i]==1)
uinsert(b[c[i]]);//,dinsert(b[c[i]]);
else
an[i]=ans;
}
for(int i=1;i<=t;i++)
if(ms[i]==2)
printf("%.2lf\n",an[i]);
return 0;
}原文：https://www.cnblogs.com/nianheng/p/10004598.html