记录编号	375615	评测结果	AAAAAAAAAA
题目名称	[HAOI 2011]防线修建	最终得分	100
用户昵称	可以的.	是否通过	通过
代码语言	C++	运行时间	0.534 s
提交时间	2017-02-25 16:49:29	内存使用	3.45 MiB

#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <ctime>
#include <cmath>
#include <set>
using namespace std;
#define Mem(a, v) memset(a, v, sizeof a)
#define Mcpy(a, b) memcpy(a, b, sizeof a)
typedef long long LL;
typedef unsigned int uint;
const int INF = 0x7f7f7f7f;
const double inf = 1e60;
const double eps = 1e-8;
const int maxn = 100010;

struct Point
{
	double x,y;
	Point(double x=0,double y=0): x(x), y(y){}
	Point(Point a,Point b){ x=b.x-a.x, y=b.y-a.y; }
	void input(){ scanf("%lf%lf", &x, &y); }
	bool operator < (const Point &b)const{
		if(x==b.x) return y<b.y;
		return x<b.x;
	}
	void out(){ printf("(%.5f  %.5f)\n", x, y);}
};
typedef Point Vector;
Vector operator + (Vector a,Vector b)
{ return Vector(a.x+b.x, a.y+b.y); }
Vector operator - (Point a,Point b)
{ return Vector(a.x-b.x, a.y-b.y); }
double operator * (Vector a,Vector b)
{ return a.x*b.y - a.y*b.x; }
double operator / (Vector a,Vector b)
{ return a.x*b.x + a.y*b.y; }
Vector operator * (Vector a,double p)
{ return Vector(a.x*p, a.y*p); }
double Length(Vector a)
{ return sqrt(a/a); }
set<Point> s;
set<Point>:: iterator l,r,it;

int n,idcnt,m;
double len,ans[maxn],dis;
struct Ques
{
	int op,x,id;
}q[maxn];
bool del[maxn];
Point c,a[maxn];

void Add_point(Point p){
	r = s.lower_bound(p); l = r; l -- ;
	if(Vector((*r),(*l))*Vector((*r),p) >= 0) return;
	dis -= Length(Vector((*l),(*r)));
	while(1){
		if(l == s.begin()) break;
		it = l; it--;
		if(Vector(p,(*l))*Vector(p,(*it)) < 0){
			dis -= Length(Vector((*it),(*l)));
			s.erase(l);
			l = it;
		} else break;
	}
	while(1){
		it = r; it ++ ;
		if(it == s.end()) break;
		if(Vector(p,(*it))*Vector(p,(*r)) < 0){
			dis -= Length(Vector((*it),(*r)));
			s.erase(r);
			r = it;
		} else break;
	}
	s.insert(p);
	it = s.find(p);
	l = it; l -- ; r = it; r ++ ;
	dis += Length(Vector(p,(*l))) + Length(Vector(p,(*r)));
}	
int main(){
#define HAHA LALA
#ifdef HAHA
	freopen("defense.in","r",stdin);
	freopen("defense.out","w",stdout);
#endif
	scanf("%lf", &len);
	c.input();
	s.insert(Point(0,0));
	s.insert(Point(len,0));
	s.insert(c);
	dis = Length(Point(0,0)-c) + Length(Point(len,0)-c);
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++ ) a[i].input();
	scanf("%d", &m);
	for(int i = 1; i <= m; i ++ ){
		scanf("%d", &q[i].op);
		if(q[i].op==1){
			scanf("%d", &q[i].x); del[q[i].x] = 1;
		} else q[i].id = ++idcnt;
	}
	for(int i = 1; i <= n; i ++ )
		if(!del[i]) Add_point(a[i]);
	for(int i = m; i; i -- )
		if(q[i].op == 1) Add_point(a[q[i].x]);
		 else ans[q[i].id] = dis;
	for(int i = 1; i <= idcnt; i ++ )
		printf("%.2f\n", ans[i]);
	return 0;
}