提交信息链接

我是按x排序，x相同再按y排序，set维护点集，询问离线，倒着加入点动态维护上凸壳，新进来一个点的时候，它向左右延申，把需要删的删了，更新答案

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=2e5+5;
typedef long long ll;
typedef double db;
struct P{
	ll x,y;
	P(ll a=0,ll b=0):x(a),y(b){}
	P operator + (P b) const {return P(x+b.x,y+b.y);}
	P operator - (P b) const {return P(x-b.x,y-b.y);}
	void show()const{printf("(%d,%d) ",x,y);}
	bool operator == (const P &b)const{
		return x==b.x&&y==b.y;
	}
}a[N];
ll cross(P a,P b){
	return a.x*b.y-a.y*b.x;
}
db dis(P a,P b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool operator < (const P &a,const P &b){
	return a.x<b.x||a.x==b.x&&a.y<b.y;
}
set<P>s;
struct QQ{
	int op,x;
}q[M];
int X,A,B,n,m;
db now,ans[N];
bool vis[N];
void add(P p){
//	printf("Add ");p.show();puts("");
	s.insert(p);
	auto it=s.find(p);
//	printf("show set : ");for(auto x:s)x.show();puts("");
	if(cross(p-*prev(it),*next(it)-p)>=0){
		s.erase(it);
		return;
	}
//	printf("+%.2lf+%.2lf-%.2lf\n",dis(p,*next(it)),dis(p,*prev(it)),dis(*prev(it),*next(it)));
	now+=dis(p,*next(it))+dis(p,*prev(it))-dis(*prev(it),*next(it));
	auto it1=next(it);
	auto it2=next(it1);
	while(it2!=s.end()){
//		printf("it1=(%lld,%lld),it2=(%lld,%lld)\n",it1->x,it1->y,it2->x,it2->y);
		if(cross(*it1-p,*it2-p)>=0){
//			printf("+%.2lf-%.2lf-%.2lf\n",dis(p,*it2),dis(*it1,*it2),dis(p,*it1));
			now+=dis(p,*it2)-dis(*it1,*it2)-dis(p,*it1);
			s.erase(it1);
			it1=it2;
			++it2;
		}
		else{
			break;
		}
	}
	it1=prev(it);
	it2=prev(it1);
	while(it1!=s.begin()){
//		printf("it1=(%lld,%lld),it2=(%lld,%lld)\n",it1->x,it1->y,it2->x,it2->y);
		if(cross(*it1-p,*it2-p)<=0){
//			printf("+%.2lf-%.2lf-%.2lf\n",dis(p,*it2),dis(*it1,*it2),dis(p,*it1));
			now+=dis(p,*it2)-dis(*it1,*it2)-dis(p,*it1);
			s.erase(it1);
			it1=it2;
			--it2;
		}
		else{
			break;
		}
	}
}
int main(){
	scanf("%d%d%d",&X,&A,&B);
	s.insert(P(0,0));
	s.insert(P(X,0));
	s.insert(P(A,B));
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%lld%lld",&a[i].x,&a[i].y);
	scanf("%d",&m);
	for(int i=1;i<=m;++i){
		scanf("%d",&q[i].op); ans[i]=-1;
		if(q[i].op==1){
			scanf("%d",&q[i].x);
			vis[q[i].x]=1;
		}
	}
	now=dis(P(0,0),P(A,B))+dis(P(A,B),P(X,0));
	for(int i=1;i<=n;++i){
		if(!vis[i]){
			add(a[i]);
		}
	}
	for(int i=m;i;--i){
		if(q[i].op==1){
			add(a[q[i].x]);
		}
		else{
			ans[i]=now;
		}
	}
	for(int i=1;i<=m;++i){
		if(q[i].op==2){
			printf("%.2lf\n",ans[i]);
		}
	}
}