记录编号	55188	评测结果	AAAAAAAAAA
题目名称	[HAOI 2011]防线修建	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.856 s
提交时间	2013-03-16 14:37:49	内存使用	1.94 MiB

#include<iostream>
#include<cstdio>
#include<set>
#include<deque>
#include<cmath>
#include<iomanip>
using namespace std;
class POINT{
public:
	int x,y;
	double s;//相邻两边长度
};
bool operator <(POINT a,POINT b){
	if(a.x<b.x) return 1;
	if(a.x>b.x) return 0;
	if(a.y<b.y) return 1;
	return 0;
}
bool operator ==(POINT a,POINT b){
	return a.x==b.x;
}
bool under(POINT a,POINT b,POINT s){//点s是否在线段ab下方
	if(s.x==a.x) return s.y<a.y;
	if(s.x==b.x) return s.y<b.y;
	//两个向量:s到a和s到b
	int x1=a.x-s.x,y1=a.y-s.y;
	int x2=b.x-s.x,y2=b.y-s.y;
	int temp=x1*y2-x2*y1;
	return temp<0;//<0意味着在下方
}
bool under1(POINT a,POINT b,POINT s){//点s是否在线段ab下方
	//这是用斜率写的奇葩函数......具体到这道题上是正确的
	if(s.x==a.x) return s.y<a.y;
	if(s.x==b.x) return s.y<b.y;
	double k1=(double)(s.y-a.y)/(double)(s.x-a.x);
	double k2=(double)(b.y-a.y)/(double)(b.x-a.x);
	return k1<k2;
}
double dis(POINT a,POINT b){
	double ans;
	ans=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
	return sqrt(ans);
}
set<POINT> hull;//凸包
deque<POINT> city;//每个城市
int m,q;//m个城市,q个修改和询问
int mark[200001]={0},data[200001]={0};//mark是标识符,data是城市编号
bool uninc[100010]={0};
deque<double> ans;
double sum;
void out(void){
	set<POINT> ::iterator km;
	km=hull.begin();
	while(km!=hull.end()){
		cout<<(*km).x<<" "<<(*km).y<<endl;
		km++;
	}
	cout<<endl;
}
void add(POINT s){//把点s加入凸包
	hull.insert(s);
	set<POINT> ::iterator now,left,right,last;
	now=hull.find(s);
	left=right=now;
	left--,right++;
	if(under(*left,*right,*now)){//已在包内
		hull.erase(now);
		return;
	}
	sum-=dis(*left,*right);
	sum+=dis(*left,*now)+dis(*now,*right);
	last=left;
	if(last==hull.begin()) goto NEXT;
	left--;
	while(under(*left,*now,*last)){//把last这个点删掉
		if(last==hull.begin()) break;
		sum-=dis(*now,*last)+dis(*last,*left);
		sum+=dis(*now,*left);
		hull.erase(last);
		if(left==hull.begin()) break;
		last=left;
		left--;
	}
	NEXT:;
	last=right;
	right++;
	if(right==hull.end()) goto END;
	while(under(*now,*right,*last)){//把last这个点删掉
		if(right==hull.end()){
			break;
		}
		sum-=dis(*now,*last)+dis(*last,*right);
		sum+=dis(*now,*right);
		hull.erase(last);
		last=right;
		right++;//这一句开始写成left了,然后调了两天!!!!!!!!!!!!!!!!!!!!
		if(right==hull.end()){
			break;
		}
	}
	END:;
}
 
void read(void){
	int n,x,y;
	scanf("%d%d%d",&n,&x,&y);
	//三个点(0,0),(n,0),(x,y)
	POINT temp;
	temp.x=temp.y=0;
	city.push_back(temp);
	temp.x=n,temp.y=0;
	city.push_back(temp);
	temp.x=x,temp.y=y;
	city.push_back(temp);
	scanf("%d",&m);
	int i;
	for(i=0;i<m;i++){
		scanf("%d%d",&temp.x,&temp.y);
		city.push_back(temp);
	}
	m+=3;
	city[0].s=dis(city[0],city[2]);
	city[1].s=dis(city[1],city[2]);
	sum=city[2].s=city[0].s+city[1].s;
	hull.insert(city[0]);
	hull.insert(city[1]);
	hull.insert(city[2]);//最初的三个城市加进去
	//0和1是两个河边,2是首都
	scanf("%d",&q);
	for(i=0;i<q;i++){
		scanf("%d",&mark[i]);
		if(mark[i]==1){
			scanf("%d",&data[i]);
			data[i]+=2;
			uninc[data[i]]=true;
		}
	}
	for(i=3;i<m;i++){
		if(!uninc[i]) add(city[i]);
	}
}
double count(void){
	set<POINT> ::iterator km,last;
	last=km=hull.begin();
	km++;
	double ans=0;
	while(km!=hull.end()){
		ans+=dis(*last,*km);
		last=km;
		km++;
	}
	return ans;
}
void work(void){
	int i;
	for(i=q-1;i>=0;i--){
		if(mark[i]==2) ans.push_front(sum);
		else add(city[data[i]]);
		set<POINT> ::iterator km;
		km=hull.begin();
	}
}
void write(void){
	int i;
	for(i=0;i<ans.size();i++) cout<<ans[i]<<endl;
}
int main(){
	freopen("defense.in","r",stdin);
	freopen("defense.out","w",stdout);
	cout<<setiosflags(ios::fixed)<<setprecision(2);
	read();
	work();
	write();
	return 0;
}