| 记录编号 |
375239 |
评测结果 |
WWWWWWWWWW |
| 题目名称 |
[HAOI 2011]防线修建 |
最终得分 |
0 |
| 用户昵称 |
 liu_runda |
是否通过 |
未通过 |
| 代码语言 |
C++ |
运行时间 |
0.477 s |
| 提交时间 |
2017-02-24 21:38:47 |
内存使用 |
16.69 MiB |
显示代码纯文本
#include<cstdio>
#include<cstdlib>
#include<cmath>
const double eps=1e-8;
int cmp(double x){return x<-eps?-1:x>eps;}
const int maxn=200005;
bool del[maxn];
int x[maxn],y[maxn];
int typ[maxn],num[maxn];double ans[maxn];
double now;
struct point{
double x,y;point(){}
point(double a,double b){x=a;y=b;}
}P[maxn];
point operator -(const point &A,const point &B){return point(A.x-B.x,A.y-B.y);}
double cross(const point &A,const point &B){return A.x*B.y-A.y*B.x;}
double dot(const point &A,const point &B){return A.x*B.x+A.y*B.y;}
double length(const point &A){return sqrt(dot(A,A));}
struct node{
int key,ord,sz;
node* ch[2];
node(){}
node(int x){
key=x;ord=rand();ch[0]=ch[1]=0;sz=1;
}
void update(){
sz=1;
if(ch[0])sz+=ch[0]->sz;
if(ch[1])sz+=ch[1]->sz;
}
}t[maxn*2];int tot=0;
node* newnode(int x){
t[++tot]=node(x);
return t+tot;
}
node* root;
void rot(node* &rt,int t){
node* c=rt->ch[t];rt->ch[t]=c->ch[t^1];c->ch[t^1]=rt;rt=c;
rt->ch[t^1]->update();rt->update();
}
void Insert(node* &rt,int x){
if(!rt){
rt=newnode(x);
}else{
int t=x>rt->key;
Insert(rt->ch[t],x);
rt->update();
if(rt->ch[t]->ord>rt->ord)rot(rt,t);
}
}
int pred(node* rt,int x){
if(!rt)return -1;
if(rt->key>=x)return pred(rt->ch[0],x);
else{
int tmp=pred(rt->ch[1],x);
if(tmp==-1)return rt->key;
else return tmp;
}
}
int succ(node* rt,int x){
if(!rt)return -1;
if(rt->key<=x)return succ(rt->ch[1],x);
else{
int tmp=succ(rt->ch[0],x);
if(tmp==-1)return rt->key;
else return tmp;
}
}
void Remove(node* &rt,int x){
if(rt->key!=x){
int t=x>rt->key;
Remove(rt->ch[t],x);
rt->update();
}else{
if(!rt->ch[0])rt=rt->ch[1];
else if(!rt->ch[1])rt=rt->ch[0];
else{
int t=rt->ch[1]->ord>rt->ch[0]->ord;
rot(rt,t);
Remove(rt->ch[t^1],x);
rt->update();
}
}
}
bool onhull[maxn];int c[maxn];
int main(){
freopen("defense.in","r",stdin);
freopen("defense.out","w",stdout);
int n,x0,y0;scanf("%d%d%d",&n,&x0,&y0);
P[0]=point(0,0);P[n]=point(n,0);P[x0]=point(x0,y0);
int m;scanf("%d",&m);
for(int i=1;i<=m;++i){
scanf("%d%d",x+i,y+i);
}
int q;scanf("%d",&q);
for(int i=1;i<=q;++i){
scanf("%d",&typ[i]);
if(typ[i]==1){
scanf("%d",&num[i]);del[num[i]]=true;
}
}
now=length(P[0]-P[x0])+length(P[n]-P[x0]);
Insert(root,0);Insert(root,x0);Insert(root,n);
onhull[x0]=true;c[x0]=0;
for(int i=q;i>=1;--i){
if(typ[i]==2)ans[i]=now;
else{
if(onhull[x[num[i]]]){
int old=c[x[num[i]]];point oldP=P[x[num[i]]];
if(y[num[i]]<y[old])continue;
else{
P[x[num[i]]]=point(x[num[i]],y[num[i]]);c[x[num[i]]]=num[i];
int suc1=succ(root,x[num[i]]),suc2=succ(root,suc1);
now-=length(oldP-P[suc1]);
while(suc2!=-1&&cmp(cross(P[suc1]-P[x[num[i]]],P[suc2]-P[x[num[i]]]))>0){
Remove(root,suc1);now-=length(P[suc1]-P[suc2]);
onhull[suc1]=false;
suc1=suc2;suc2=succ(root,suc2);
}
now+=length(P[suc1]-P[x[num[i]]]);
int pre1=pred(root,x[num[i]]),pre2=pred(root,pre1);
now-=length(oldP-P[pre1]);
while(pre2!=-1&&cmp(cross(P[pre1]-P[x[num[i]]],P[pre2]-P[x[num[i]]]))<0){
Remove(root,pre1);now-=length(P[pre1]-P[pre2]);
onhull[pre1]=false;
pre1=pre2;pre2=pred(root,pre2);
}
now+=length(P[pre1]-P[x[num[i]]]);
}
}else{
int pre1=pred(root,x[num[i]]),suc1=succ(root,y[num[i]]);
if(cmp(cross(point(x[num[i]],y[num[i]])-P[pre1],P[suc1]-P[pre1]))>=0)continue;
else{
onhull[x[num[i]]]=true;Insert(root,x[num[i]]);P[x[num[i]]]=point(x[num[i]],y[num[i]]);
now-=length(P[pre1]-P[suc1]);
int suc2=succ(root,suc1);
while(suc2!=-1&&cmp(cross(P[suc1]-P[x[num[i]]],P[suc2]-P[x[num[i]]]))>0){
Remove(root,suc1);now-=length(P[suc1]-P[suc2]);
onhull[suc1]=false;
suc1=suc2;suc2=succ(root,suc2);
}
now+=length(P[suc1]-P[x[num[i]]]);
int pre2=pred(root,pre1);
while(pre2!=-1&&cmp(cross(P[pre1]-P[x[num[i]]],P[pre2]-P[x[num[i]]]))<0){//printf("pre1==%d\n",pre1);
Remove(root,pre1);now-=length(P[pre1]-P[pre2]);
onhull[pre1]=false;
pre1=pre2;pre2=pred(root,pre2);
}
now+=length(P[pre1]-P[x[num[i]]]);
}
}
}
}
for(int i=1;i<=q;++i){
if(typ[i]==2)printf("%.2f\n",ans[i]);
}
fclose(stdin);fclose(stdout);
return 0;
}