记录编号	358011	评测结果	AAAAAAAAAA
题目名称	[HAOI 2011]防线修建	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.486 s
提交时间	2016-12-13 19:47:30	内存使用	3.45 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;
const int N=1e5+10;
typedef double db;
const db eps=1e-9;
struct point{
	db x,y;
	point(db X=0,db Y=0){x=X;y=Y;}
	void init(){scanf("%lf%lf",&x,&y);}
	bool operator > (const point a)const{return abs(x-a.x)<=eps?y>a.y:x>a.x;}
	bool operator < (const point a)const{return abs(x-a.x)<=eps?y<a.y:x<a.x;}
	bool operator == (const point a)const{return abs(x-a.x)<=eps&&abs(y-a.y)<=eps;}
}p[N];
db k(point x,point y){
	if (abs(x.x-y.x)<=eps) return x.y<y.y?1e9:-1e9;
	return (x.y-y.y)/(x.x-y.x);
}
db sqr(db x){return x*x;}
db dis(point x,point y){
	return sqrt(sqr(x.x-y.x)+sqr(x.y-y.y));
}
class tb{
	set<point> S;db len;
	typedef set<point>::iterator It;
	void del(It l,It x,It r){
		len-=dis(*l,*x);
		len-=dis(*x,*r);
		len+=dis(*l,*r);
		S.erase(x);
	}
public:
	void print(It x){
		point v=*x;
		printf("%lf %lf\n",v.x,v.y);
	}
	void init(){
		int n,x,y;
		scanf("%d%d%d",&n,&x,&y);
		S.insert(point(-1,-1e9));
		S.insert(point(0,0));
		S.insert(point(n,0));
		S.insert(point(n+1,-1e9));
		len=n;
		insert(point(x,y));
	}
	void insert(point v){
		S.insert(v);
		It x=S.find(v),l=x,r=x;
		--l;++r;
		len-=dis(*l,*r);
		len+=dis(*l,*x);
		len+=dis(*x,*r);
		while (1){
			It ll=l;--ll;
			if (k(*ll,*l)>k(*l,*x)) break;
			del(ll,l,x);
			l=ll;
		}
		while (1){
			It rr=r;++rr;
			if (k(*x,*r)>k(*r,*rr)) break;
			del(x,r,rr);
			r=rr;
		}
		if (k(*l,*x)>k(*x,*r)) return;
		del(l,x,r);
	}
	db L(){return len;}
}T;
bool vis[N];
int m,q,tp[N],pos[N];
db ans[N];
int main()
{
	freopen("defense.in","r",stdin);
	freopen("defense.out","w",stdout);
	T.init();
	scanf("%d",&m);
	for (int i=1;i<=m;i++) p[i].init();
	scanf("%d",&q);
	for (int i=1;i<=q;i++){
		scanf("%d",&tp[i]);
		if (tp[i]==1){
			scanf("%d",&pos[i]);
			vis[pos[i]]=1;
		}
	}
	for (int i=1;i<=m;i++)
	if (!vis[i]) T.insert(p[i]);
	for (int i=q;i;i--)
	if (tp[i]==1) T.insert(p[pos[i]]);
		else ans[i]=T.L();
	for (int i=1;i<=q;i++)
	if (tp[i]==2) printf("%.2lf\n",ans[i]);
	return 0;
}