记录编号	275563	评测结果	AAAAAAAAAA
题目名称	[HAOI 2011]防线修建	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.211 s
提交时间	2016-07-02 16:29:19	内存使用	5.08 MiB

# define maxn 200010ul

# include <set>
# include <cmath>
# include <stdio.h>
# include <iostream>
# include <algorithm>

# define fi first
# define se second

# define mp(a,b) std::make_pair((a),(b))

typedef std::pair<int,int> PII;
typedef std::set<PII>::iterator iter;

std::set<PII> Gap;

inline double sqr(double x) { return x*x; }
double dist(const PII &a,const PII &b) { return std::sqrt(sqr(a.fi-b.fi)+sqr(a.se-b.se)); }
PII operator + (const PII &a,const PII &b) { return mp(a.fi+b.fi,a.se+b.se); }
PII operator - (const PII &a,const PII &b) { return mp(a.fi-b.fi,a.se-b.se); }
double operator * (const PII &a,const PII &b) { return a.fi*b.se-a.se*b.fi; }

void read(int &x) {
	x=0; int c=getchar(),f=0; for(;c<'0'||c>'9';c=getchar()) f|=(c=='-');
	for(;c>='0'&&c<='9';c=getchar()) x=(x*10)+(c^48); if(f) x=-x; return;
}

int n,m,q,a[maxn][2],c[maxn][2]; double sum,ans[maxn]; bool b[maxn];

void del(iter x) {
	iter u=x,v=x; u--,v++;
	sum-=dist(*u,*x)+dist(*x,*v);
	sum+=dist(*u,*v); Gap.erase(x); return;
}

void ins(PII x){
	iter it=Gap.upper_bound(x); --it;
	iter v=it,u; ++v; if((x-*it)*(*v-*it)>=0) return;
	Gap.insert(x); it=Gap.find(x); v=it,u=it; u--,v++;
	sum+=dist(*u,*it)+dist(*it,*v); sum-=dist(*u,*v);
	for(v=it;;v=it) {
		++v,u=v,++v;
		if(v==Gap.end()||((*u-*it)*(*v-*it))<0) break;
		del(u);
	} for(v=it;;v=it){
		--v; if(v==Gap.begin()) break;
		u=v,--v; if(((*u-*v)*(*it-*v))<0) break;
		del(u);
	} return;
}

int main() {
	freopen("defense.in","r",stdin),freopen("defense.out","w",stdout);
	read(n),read(a[0][0]),read(a[0][1]),read(m);
	for(int i=1;i<=m;i++) read(a[i][0]),read(a[i][1]);
	read(q); for(int i=1;i<=q;i++) {
		read(c[i][0]);
		if(c[i][0]==1) read(c[i][1]),b[c[i][1]]=1;
	} Gap.insert(mp(0,0)),Gap.insert(mp(n,0)); sum=n;
	for(int i=0;i<=m;i++) if(!b[i]) ins(mp(a[i][0],a[i][1]));
	for(int i=q;i;i--) {
		if(c[i][0]==1) ins(mp(a[c[i][1]][0],a[c[i][1]][1]));
		else ans[i]=sum;
	} for(int i=1;i<=q;i++) if(ans[i]>1e-9) printf("%.2lf\n",ans[i]); return 0;
}