记录编号	241422	评测结果	AAAAAAAAAA
题目名称	[HAOI 2011]防线修建	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	0.261 s
提交时间	2016-03-25 11:58:04	内存使用	27.02 MiB

#include<iostream>
#include<cstdio>
#include<set>
#include<cmath>
using namespace std;
const int maxn = 1e6+10;
int n, m, q;
int del[maxn];

inline int get_num() {
	int ans = 0;
	char tmp = getchar();
	while(tmp < '0' || tmp > '9') tmp = getchar();
	while(tmp <= '9' && tmp >= '0') {
		ans = ans*10 + tmp - '0';
		tmp = getchar();
	}
	return ans;
}

struct question {
	bool ques;
	int tar;
	double ans;
	question() {}
	question(bool is_, int tar_) { ques = is_, tar = tar_; }
}qs[maxn];


struct node {
	int x, y;
	node() {}
	node(int x_, int y_) { x = x_, y = y_; }
	inline bool operator < (const node &b) const {
		return x == b.x ? y < b.y : x < b.x;
	} 
	inline node operator - (const node &b) const{//得到a->b的node向量 
		return node(b.x-x, b.y-y);
	}
	inline int operator * (const node &b) const{
		return x*b.y - y*b.x;
	} 
}ns[maxn];


class Convex_hull {
private:
	set<node> ns;
	double tot;
public:
	inline void init(int x, int y) {
		ns.insert(node(0, 0));
		ns.insert(node(n, 0));
		ns.insert(node(x, y));
		tot = dis(node(x, y), node(0, 0)) + dis(node(x, y), node(n, 0));
	}
	inline double dis(node a, node b) {
		return sqrt((double)((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
	}
	inline void rebuild(set<node>::iterator tar) {
		set<node>::iterator it = tar;
		it--;
		node l = *(it);//当前连接节点 
		while(it != ns.begin()) {
			it--;
			node ne = *(it);//下一个节点
			if((l - *tar) * (ne - *tar) > 0) break; //到下一个点的连线在凸包内部，更新左节点结束 
			tot -= dis(l, ne);
			ns.erase(l);
			l = ne;
		}
		it = tar;
		it++; 
		node r = *(it);//当前连接节点 
		set<node>::iterator end = ns.end();
		end--; 
		while(it != end) {
			it++;
			node ne = *(it);//下一个节点
			if((r - *tar) * (ne - *tar) < 0) break; //到下一个点的连线在凸包内部，更新左节点结束 
			tot -= dis(r, ne);
			ns.erase(r);
			r = ne;
		}
		tot += dis(*tar, l) + dis(*tar, r);
	}
	inline void insert(node tar) {
		ns.insert(tar);
		set<node>::iterator it;
		it = ns.find(tar);
		it--;
		node l = *(it);
		it++, it++;
		node r = *(it);
		if((r - l) * (tar - l) < 0) {//如果在凸包内部则不需要更新 
			ns.erase(tar);
			return;
		}
		tot -= dis(l, r);
		it--;
		rebuild(it); 
	}
	inline double now_ans() {
		return tot;
	}
}ch; 


inline void read() {
	int x, y;
	n = get_num();
	x = get_num();
	y = get_num();
	m = get_num();
	ch.init(x, y);
	for(int i = 1; i <= m; i++) {
		x = get_num();
		y = get_num();
		ns[i] = node(x, y);
	}
	q = get_num();
	int is;
	for(int i = 1; i <= q; i++) {
		is = get_num();
		if(is == 2) {
			qs[i] = question(1, 0);
		} else {
			x = get_num();
			qs[i] = question(0, x);
			del[x] = true;
		}
	} 
} 


inline void solve() {
	for(int i = 1; i <= m; i++) {
		if(del[i]) continue;
		ch.insert(ns[i]);
	}
	for(int i = q; i >= 1; i--) {//倒叙后加点 
		if(qs[i].ques) qs[i].ans = ch.now_ans();
		else {
			ch.insert(ns[qs[i].tar]);
		}
	}
	for(int i = 1; i <= q; i++) {//正序输出 
		if(qs[i].ques) printf("%.2lf\n", qs[i].ans);
	}
}
int main() {
	freopen("defense.in", "r", stdin);
	freopen("defense.out", "w", stdout);
	read();
	solve();
	return 0;
}