Advertisement
yicongli

LG2521

Mar 11th, 2019
132
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.78 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define db double
  8.  
  9. template<typename T>
  10. inline void read(T&x){
  11.     x=0;T k=1;char gc;
  12.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  13.     while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
  14. }
  15.  
  16. const int N=200005;
  17.  
  18. struct Point{
  19.     int x,y;
  20.    
  21.     inline bool operator <(const Point &A)const{
  22.         return x==A.x?y<A.y:x<A.x;
  23.     }
  24. }P[N];
  25.  
  26. inline Point operator - (const Point &A,const Point &B){
  27.     return Point{A.x-B.x,A.y-B.y};
  28. }
  29.  
  30. inline int operator * (const Point &A,const Point &B){
  31.     return A.x*B.y-A.y*B.x;
  32. }
  33.  
  34. inline db sqr(db x){
  35.     return x*x;
  36. }
  37.  
  38. inline db dist(const Point &A,const Point &B){
  39.     return sqrt(sqr(A.x-B.x)+sqr(A.y-B.y));
  40. }
  41.  
  42. struct Query{
  43.     int t,x;
  44. }Q[N];
  45.  
  46. set<Point>S;
  47. db ans;
  48.  
  49. inline void insert(const Point &A){
  50.     set<Point>::iterator l=S.lower_bound(A),r=l,t;
  51.     --l;
  52.     if((*l-A)*(*r-A)<0)return ;
  53.     ans-=dist(*l,*r);
  54.     while(1){
  55.         t=r,++r;
  56.         if(r==S.end()||(*t-A)*(*r-A)<0)break;
  57.         ans-=dist(*t,*r);
  58.         S.erase(t);
  59.     }
  60.     while(1){
  61.         t=l,--l;
  62.         if(t==S.begin()||(*l-A)*(*t-A)<0)break;
  63.         ans-=dist(*l,*t);
  64.         S.erase(t);
  65.     }
  66.     S.insert(A);
  67.     l=r=S.find(A);
  68.     l--;r++;
  69.     ans+=dist(*l,A);
  70.     ans+=dist(A,*r);
  71. }
  72.  
  73. bool vis[N];
  74. db Ans[N];
  75.  
  76. int main(){
  77. //  freopen(".in","r",stdin);
  78. //  freopen(".out","w",stdout);
  79.     int n,x,y;r(n),r(x),r(y);
  80.     int m;r(m);
  81.     for(int i=1;i<=m;++i){
  82.         r(P[i].x),r(P[i].y);
  83.     }
  84.     int q;r(q);
  85.     for(int i=1;i<=q;++i){
  86.         int type,x;r(type);
  87.         if(type==1){
  88.             r(x);
  89.             vis[x]=1;
  90.         }
  91.         Q[i]=Query{type,x};
  92.     }
  93.     Point A{0,0};
  94.     Point B{n,0};
  95.     Point C{x,y};
  96.     ans+=dist(A,C);
  97.     ans+=dist(B,C);
  98.     S.insert(A);
  99.     S.insert(B);
  100.     S.insert(C);
  101.     for(int i=1;i<=m;++i){
  102.         if(!vis[i])insert(P[i]);
  103.     }
  104.     for(int i=q;i;--i){
  105.         if(Q[i].t==2)Ans[i]=ans;
  106.         else insert(P[Q[i].x]);
  107.     }
  108.     for(int i=1;i<=q;++i){
  109.         if(Q[i].t==2)printf("%.2lf\n",Ans[i]);
  110.     }
  111.     return 0;
  112. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement