记录编号	157554	评测结果	AAAAAAAAAA
题目名称	[HAOI 2011]防线修建	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.221 s
提交时间	2015-04-09 11:54:21	内存使用	5.65 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <algorithm>
#include <cmath>
using namespace std;
#define getc() getchar()
#define SetFile(x) (freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout))
template<class T>inline void getd(T &x){
    char ch = getc();bool neg = false;
    while(!isdigit(ch) && ch != '-')ch = getc();
    if(ch == '-')ch = getc(), neg = true;
    x = ch - '0';
    while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
    if(neg)x = -x;
}
/***********************************************************************/
#include <set>
#include <cmath>
const int maxn = 100003, qcnt = 200003;
const double eps = 1e-10;
struct Point{int x, y;}P[maxn];
typedef Point Vector;
typedef set<Point> Set;
Set S;

inline bool operator < (const Point &a, const Point &b){
	return a.x != b.x ? a.x < b.x : a.y < b.y;
}
inline Vector operator - (const Point &a, const Point &b){return (Vector){a.x-b.x, a.y-b.y};}
inline double Length(const Vector &v){return sqrt(v.x * v.x + v.y * v.y + 0.0);}
inline double dis(const Point &a, const Point &b){return Length(a - b);}
inline bool operator * (const Vector &a, const Vector &b){return a.y * b.x > a.x * b.y;}
#define check(a, b, c) ((b - a) * (c - b))
double Ans, ans[qcnt];
int n, x, y, m, q, Q[qcnt];
double opt[qcnt], del[maxn];

inline void insert(const Point &a){
	Set::iterator it, l, r;l = S.lower_bound(a);r = l--;
	if(!check(*l, a, *r))return;
	Ans -= dis(*l, *r);
	it = l;--it;
	while(it != S.end() && !check(*it, *l, a)){
		Ans -= dis(*l, *it);
		S.erase(l--);
		--it;
	}
	it = r;++it;
	while(it != S.end() && !check(a, *r, *it)){
		Ans -= dis(*it, *r);
		S.erase(r++);
		++it;
	}
	Ans += dis(*l, a) + dis(*r, a);
	S.insert(a);
}
inline void init(){
	getd(n), getd(x), getd(y), getd(m);
	int i, t;
	for(i = 1;i <= m;++i)getd(P[i].x), getd(P[i].y);
	getd(q);
	for(i = 1;i <= q;++i){
		getd(t);opt[i] = --t;
		if(!t)getd(Q[i]), del[Q[i]] = true;
	}
	Point 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(i = 1;i <= m;++i)if(!del[i])insert(P[i]);
}

inline void work(){
	int i;
	for(i = q;i;--i){
		if(opt[i])ans[i] = Ans;
		else insert(P[Q[i]]);
	}
	for(i = 1;i <= q;++i)if(opt[i])printf("%.2lf\n", ans[i] + eps);
}

int main(){
	#ifdef DEBUG
	freopen("test.txt", "r", stdin);
	#else
	SetFile(defense);
	#endif
	
	init();
	work();
 
#ifdef DEBUG
    printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);
#endif
    return 0;
}