Advertisement
yicongli

BZ1249

Mar 11th, 2019
141
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.40 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 ll long long
  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=100005;
  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;
  23.     }
  24.    
  25.     inline bool operator <(const Point &A)const{
  26.         return x==A.x?y<A.y:x<A.x;
  27.     }
  28. }P[N];
  29.  
  30. inline Point operator - (const Point &A,const Point &B){
  31.     return Point{A.x-B.x,A.y-B.y};
  32. }
  33.  
  34. inline ll operator * (const Point &A,const Point &B){
  35.     return (ll)A.x*B.y-(ll)A.y*B.x;
  36. }
  37.  
  38. inline ll area(const Point &A,const Point &B,const Point &C){
  39.     return abs((C-A)*(B-A));
  40. }
  41.  
  42. ll ans;
  43. set<Point>S1;
  44. set<Point>::iterator l,r,t;
  45. inline void insert1(const Point &x){
  46.     r=S1.lower_bound(x);
  47.     --(l=r);
  48.     if(r==S1.end()){
  49.         while(l!=S1.begin()&&((*--(t=l)-x)*(*l-x)>=0)){
  50.             ans+=(*t-x)*(*l-x);
  51.             S1.erase(l);
  52.             l=t;
  53.         }
  54.         S1.insert(x);
  55.         return ;
  56.     }
  57.     if(*r==x)return ;
  58.     if(r==S1.begin()){
  59.         while(++(t=r)!=S1.end()&&(*r-x)*(*t-x)>=0){
  60.             ans+=(*r-x)*(*t-x);
  61.             S1.erase(r);
  62.             r=t;
  63.         }
  64.         S1.insert(x);
  65.         return ;
  66.     }
  67.     if((*l-x)*(*r-x)<=0)return ;
  68.     ans+=(*l-x)*(*r-x);
  69.     while(l!=S1.begin()&&((*--(t=l)-x)*(*l-x)>=0)){
  70.         ans+=(*t-x)*(*l-x);
  71.         S1.erase(l);
  72.         l=t;
  73.     }
  74.     while(++(t=r)!=S1.end()&&(*r-x)*(*t-x)>=0){
  75.         ans+=(*r-x)*(*t-x);
  76.         S1.erase(r);
  77.         r=t;
  78.     }
  79.     S1.insert(x);
  80. }
  81.  
  82. set<Point>S2;
  83. inline void insert2(const Point &x){
  84.     r=S2.lower_bound(x);
  85.     --(l=r);
  86.     if(r==S2.end()){
  87.         while(l!=S2.begin()&&((*--(t=l)-x)*(*l-x)<=0)){
  88.             ans-=(*t-x)*(*l-x);
  89.             S2.erase(l);
  90.             l=t;
  91.         }
  92.         S2.insert(x);
  93.         return ;
  94.     }
  95.     if(*r==x)return ;
  96.     if(r==S2.begin()){
  97.         while(++(t=r)!=S2.end()&&(*r-x)*(*t-x)<=0){
  98.             ans-=(*r-x)*(*t-x);
  99.             S2.erase(r);
  100.             r=t;
  101.         }
  102.         S2.insert(x);
  103.         return ;
  104.     }
  105.     if((*l-x)*(*r-x)>=0)return ;
  106.     ans-=(*l-x)*(*r-x);
  107.     while(l!=S2.begin()&&((*--(t=l)-x)*(*l-x)<=0)){
  108.         ans-=(*t-x)*(*l-x);
  109.         S2.erase(l);
  110.         l=t;
  111.     }
  112.     while(++(t=r)!=S2.end()&&(*r-x)*(*t-x)<=0){
  113.         ans-=(*r-x)*(*t-x);
  114.         S2.erase(r);
  115.         r=t;
  116.     }
  117.     S2.insert(x);
  118. }
  119.  
  120. inline void insert(const Point &A){
  121.     insert1(A);
  122.     insert2(A);
  123. }
  124.  
  125. int main(){
  126.     int x,y;
  127.     for(int i=1;i<=2;++i){
  128.         r(x),r(y);
  129.         S1.insert(Point{x,y});
  130.         S2.insert(Point{x,y});
  131.     }
  132.     r(x),r(y);
  133.     insert(Point{x,y});
  134.     int n;r(n);
  135.     while(n--){
  136.         r(x),r(y);
  137.         insert(Point{x,y});
  138.         printf("%lld\n",ans);
  139.     }
  140.     return 0;
  141. }
  142. /*
  143. 0 0 1 1 -1 0
  144. 5
  145. 1 0
  146. 0 1
  147. -1 -1
  148. 1 2
  149. 2 -1
  150.  
  151. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement