记录编号	533157	评测结果	AAAAAAAAAA
题目名称	[HAOI 2011]防线修建	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.512 s
提交时间	2019-06-18 13:14:13	内存使用	17.67 MiB

#include<bits/stdc++.h>
#define IT set<node>::iterator
#define check(a,b,c) ((b-a)*(c-b))
using namespace std;
const int N=1e5+7;
const int M=2e5+7;
const double eps=1e-10;
int m,n,x,y,q;
int opt[M],Q[M];
bool vis[M];
double ans[N],Ans;
struct node
{
	double x,y;
} pt[N];
set<node> s;
bool operator< (const node &a,const node &b)
{
	return a.x!=b.x?a.x<b.x:a.y<b.y;
}
node operator - (const node &a,const node &b) {return (node){a.x-b.x,a.y-b.y};}
double sqr(double x) {return x*x;}
double dis(node a,node b) {return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
bool operator * (const node &a,const node &b) {return a.y*b.x>a.x*b.y;}
void insert(const node &pos)
{
	IT it,itl,itr;
	itl=s.lower_bound(pos);itr=itl--;
	if (!check(*itl,pos,*itr)) return;
	Ans-=dis(*itl,*itr);
	it=itl;it--;
	while (it!=s.end()&&!check(*it,*itl,pos))
	{
		Ans-=dis(*itl,*it);
		s.erase(itl--);
		it--;
	}
	it=itr;it++;
	while (it!=s.end()&&!check(pos,*itr,*it))
	{
		Ans-=dis(*it,*itr);
		s.erase(itr++);
		++it;
	}
	Ans+=dis(*itl,pos)+dis(*itr,pos);
	s.insert(pos);
}
int main()
{
	freopen("defense.in","r",stdin);
	freopen("defense.out","w",stdout);
	scanf("%d%d%d%d",&n,&x,&y,&m);
	for (int i=1;i<=m;i++) scanf("%lf%lf",&pt[i].x,&pt[i].y);
	scanf("%d",&q);int p;
	for (int i=1;i<=q;i++)
	{
		scanf("%d",&p);p--;opt[i]=p;
		if (!p) scanf("%d",&Q[i]),vis[Q[i]]=true;
	}
	node a={0,0},b={x,y},c={n,0};
	s.insert(a);s.insert(b);s.insert(c);
	Ans=dis(a,b)+dis(b,c);
	for (int i=1;i<=m;i++) if (!vis[i]) insert(pt[i]);
	for (int i=q;i;i--)
	{
		if (opt[i]) ans[i]=Ans;
		else insert(pt[Q[i]]);
	}
	for (int i=1;i<=q;i++) if (opt[i]) printf("%.2lf\n",ans[i]+eps);
	return 0;
}