Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define gc c=getchar()
- #define r(x) read(x)
- #define db double
- template<typename T>
- inline void read(T&x){
- x=0;T k=1;char gc;
- while(!isdigit(c)){if(c=='-')k=-1;gc;}
- while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
- }
- const int N=200005;
- struct Point{
- int x,y;
- inline bool operator <(const Point &A)const{
- return x==A.x?y<A.y:x<A.x;
- }
- }P[N];
- inline Point operator - (const Point &A,const Point &B){
- return Point{A.x-B.x,A.y-B.y};
- }
- inline int operator * (const Point &A,const Point &B){
- return A.x*B.y-A.y*B.x;
- }
- inline db sqr(db x){
- return x*x;
- }
- inline db dist(const Point &A,const Point &B){
- return sqrt(sqr(A.x-B.x)+sqr(A.y-B.y));
- }
- struct Query{
- int t,x;
- }Q[N];
- set<Point>S;
- db ans;
- inline void insert(const Point &A){
- set<Point>::iterator l=S.lower_bound(A),r=l,t;
- --l;
- if((*l-A)*(*r-A)<0)return ;
- ans-=dist(*l,*r);
- while(1){
- t=r,++r;
- if(r==S.end()||(*t-A)*(*r-A)<0)break;
- ans-=dist(*t,*r);
- S.erase(t);
- }
- while(1){
- t=l,--l;
- if(t==S.begin()||(*l-A)*(*t-A)<0)break;
- ans-=dist(*l,*t);
- S.erase(t);
- }
- S.insert(A);
- l=r=S.find(A);
- l--;r++;
- ans+=dist(*l,A);
- ans+=dist(A,*r);
- }
- bool vis[N];
- db Ans[N];
- int main(){
- // freopen(".in","r",stdin);
- // freopen(".out","w",stdout);
- int n,x,y;r(n),r(x),r(y);
- int m;r(m);
- for(int i=1;i<=m;++i){
- r(P[i].x),r(P[i].y);
- }
- int q;r(q);
- for(int i=1;i<=q;++i){
- int type,x;r(type);
- if(type==1){
- r(x);
- vis[x]=1;
- }
- Q[i]=Query{type,x};
- }
- Point A{0,0};
- Point B{n,0};
- Point C{x,y};
- ans+=dist(A,C);
- ans+=dist(B,C);
- S.insert(A);
- S.insert(B);
- S.insert(C);
- for(int i=1;i<=m;++i){
- if(!vis[i])insert(P[i]);
- }
- for(int i=q;i;--i){
- if(Q[i].t==2)Ans[i]=ans;
- else insert(P[Q[i].x]);
- }
- for(int i=1;i<=q;++i){
- if(Q[i].t==2)printf("%.2lf\n",Ans[i]);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment