Advertisement
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 ll long long
- 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=100005;
- struct Point{
- int x,y;
- inline bool operator ==(const Point &A)const{
- return x==A.x&&y==A.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 ll operator * (const Point &A,const Point &B){
- return (ll)A.x*B.y-(ll)A.y*B.x;
- }
- inline ll area(const Point &A,const Point &B,const Point &C){
- return abs((C-A)*(B-A));
- }
- ll ans;
- set<Point>S1;
- set<Point>::iterator l,r,t;
- inline void insert1(const Point &x){
- r=S1.lower_bound(x);
- --(l=r);
- if(r==S1.end()){
- while(l!=S1.begin()&&((*--(t=l)-x)*(*l-x)>=0)){
- ans+=(*t-x)*(*l-x);
- S1.erase(l);
- l=t;
- }
- S1.insert(x);
- return ;
- }
- if(*r==x)return ;
- if(r==S1.begin()){
- while(++(t=r)!=S1.end()&&(*r-x)*(*t-x)>=0){
- ans+=(*r-x)*(*t-x);
- S1.erase(r);
- r=t;
- }
- S1.insert(x);
- return ;
- }
- if((*l-x)*(*r-x)<=0)return ;
- ans+=(*l-x)*(*r-x);
- while(l!=S1.begin()&&((*--(t=l)-x)*(*l-x)>=0)){
- ans+=(*t-x)*(*l-x);
- S1.erase(l);
- l=t;
- }
- while(++(t=r)!=S1.end()&&(*r-x)*(*t-x)>=0){
- ans+=(*r-x)*(*t-x);
- S1.erase(r);
- r=t;
- }
- S1.insert(x);
- }
- set<Point>S2;
- inline void insert2(const Point &x){
- r=S2.lower_bound(x);
- --(l=r);
- if(r==S2.end()){
- while(l!=S2.begin()&&((*--(t=l)-x)*(*l-x)<=0)){
- ans-=(*t-x)*(*l-x);
- S2.erase(l);
- l=t;
- }
- S2.insert(x);
- return ;
- }
- if(*r==x)return ;
- if(r==S2.begin()){
- while(++(t=r)!=S2.end()&&(*r-x)*(*t-x)<=0){
- ans-=(*r-x)*(*t-x);
- S2.erase(r);
- r=t;
- }
- S2.insert(x);
- return ;
- }
- if((*l-x)*(*r-x)>=0)return ;
- ans-=(*l-x)*(*r-x);
- while(l!=S2.begin()&&((*--(t=l)-x)*(*l-x)<=0)){
- ans-=(*t-x)*(*l-x);
- S2.erase(l);
- l=t;
- }
- while(++(t=r)!=S2.end()&&(*r-x)*(*t-x)<=0){
- ans-=(*r-x)*(*t-x);
- S2.erase(r);
- r=t;
- }
- S2.insert(x);
- }
- inline void insert(const Point &A){
- insert1(A);
- insert2(A);
- }
- int main(){
- int x,y;
- for(int i=1;i<=2;++i){
- r(x),r(y);
- S1.insert(Point{x,y});
- S2.insert(Point{x,y});
- }
- r(x),r(y);
- insert(Point{x,y});
- int n;r(n);
- while(n--){
- r(x),r(y);
- insert(Point{x,y});
- printf("%lld\n",ans);
- }
- return 0;
- }
- /*
- 0 0 1 1 -1 0
- 5
- 1 0
- 0 1
- -1 -1
- 1 2
- 2 -1
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement