BZOJ 2300 [HAOI2011]防线修建

题目大意

请维护一个极坐标系上的点，支持：

1.删除一个节点 2.求现有的凸包的总长度。

删除节点是很难实现的任务。因为删除之后如果它在凸包上的话维护新凸包就会无从下手。

所以考虑将询问离线，倒着插入每一个点，用set维护凸包。每个点只进set出set一次所以时间复杂度$O(N \log N).$

注意细节……%GXZdalao写的又短又明朗……我根本就没写明白= =

#include <set>
#include <cmath>
#include <cstdio>
#include <cctype>
using namespace std;
#define R register
#define EPS 1e-5
#define N 100000
#define Q 200000
inline char nc()
{
	static char buf[100000],*p1,*p2;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int RI()
{
	R int ret=0;R char tmp=nc();
	while(!isdigit(tmp)) tmp=nc();
	while(isdigit(tmp)) ret=ret*10+(tmp^'0'),tmp=nc();
	return ret;
}
struct point
{
	int x,y;
	double l;
	point(){x=y=l=0;}
	point(int X,int Y){x=X,y=Y,l=0;}
	point(int X,int Y,double Z){x=X,y=Y,l=Z;}
	point operator-(const point &A)const{return point(x-A.x,y-A.y);}
	double operator*(const point &A)const{return x*A.y-y*A.x;}
	bool operator<(const point &A)const{return x==A.x?y<A.y:x<A.x;}
}p[N+1];
set<point>s;
double ans[Q+1],res=0;
inline void insert(point A)
{
	set<point>::iterator C=s.upper_bound(A);
	point B=*C--;
	if((A-*C)*(B-*C)>EPS) return;
	++C,B=*C++;
	while(C!=s.end()&&(B-A)*(*C-B)>EPS) res-=B.l,s.erase(B),B=*C++;
	B=*(--C),res-=B.l,B.l=sqrt((A.x-C->x)*(A.x-C->x)+(A.y-C->y)*(A.y-C->y)),res+=B.l;
	s.erase(C),s.insert(B);
	C=--s.upper_bound(A);
	bool flg=false;
	while((flg=true,C!=s.begin())&&(flg=false,B=*C--,(B-A)*(*C-B)<EPS)) res-=B.l,s.erase(B);
	if(!flg) C++;
	A.l=sqrt((A.x-C->x)*(A.x-C->x)+(A.y-C->y)*(A.y-C->y)),res+=A.l;
	s.insert(A);
}
int md[Q+1],tg[Q+1];
bool v[N+1];
int main()
{
	R int A=RI(),B=RI(),C=RI(),n=RI(),q;
	s.insert(point(0,0));
	s.insert(point(B,C,sqrt(B*B+C*C))),res+=sqrt(B*B+C*C);
	s.insert(point(A,0,sqrt((A-B)*(A-B)+C*C))),res+=sqrt((A-B)*(A-B)+C*C);
	for(R int i=1;i<=n;++i) p[i].x=RI(),p[i].y=RI();
	q=RI();
	for(R int i=1;i<=q;++i)
	{
		md[i]=RI();
		if(md[i]==1) tg[i]=RI(),v[tg[i]]=true;
	}
	for(R int i=1;i<=n;++i) if(!v[i]) insert(p[i]);
	for(R int i=q;i;i--)
	{
		if(md[i]==1) insert(p[tg[i]]);
		else ans[i]=res;
	}
	for(R int i=1;i<=q;++i) if(md[i]==2) printf("%.2lf\n",ans[i]);
	return 0;
}