Submission #1271397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271397		noyancanturk	SIR (COI15_sir)	C++20	0 / 100	128 ms	15084 KiB

sir

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
#define int ll
#define pb push_back

using pii=pair<int,int>;

const int lim=3e5+100;

pii x[lim],y[lim];

pii operator+(pii x,pii y){
  return {x.first+y.first,x.second+y.second};
}
pii operator-(pii x,pii y){
  return {x.first-y.first,x.second-y.second};
}
int operator*(pii x,pii y){
  return (x.second*y.first)-(y.second*x.first);
}
int cross(pii x,pii y1,pii y2){
  return (y1-x)*(y2-x);
}
ostream& operator<<(ostream&st,pii x){
  return st<<'{'<<x.first<<' '<<x.second<<'}';
}

vector<pii>convexhull(pii*a,int n){
  vector<pii>hull;
  sort(a,a+n);
  hull.pb(a[0]);
  for(int i=1;i<n;i++){
    int sz;
    while(1<(sz=hull.size())&&0>=cross(hull[sz-2],hull[sz-1],a[i])){
      hull.pop_back();
    }
    hull.pb(a[i]);
  }
  for(int i=n-2;0<=i;i--){
    int sz;
    while(1<(sz=hull.size())&&0>=cross(hull[sz-2],hull[sz-1],a[i])){
      hull.pop_back();
    }
    hull.pb(a[i]);
  }
  if(1<n)hull.pop_back();
  return hull;
}

signed main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  int n,m;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>x[i].first>>x[i].second;
  }
  cin>>m;
  for(int i=0;i<m;i++){
    cin>>y[i].first>>y[i].second;
  }
  auto a=convexhull(x,n);
  auto b=convexhull(y,m);
  n=a.size();
  m=b.size();
  // for(int i=0;i<n;i++){
  //   cerr<<a[i].first<<' '<<a[i].second<<'\n';
  // }
  // cerr<<'\n';
  // for(int i=0;i<m;i++){
  //   cerr<<b[i].first<<' '<<b[i].second<<'\n';
  // }
  // cerr<<'\n';
  int maxi=0;
  int worst=0,cur=1,area=0;
  for(int i=0;i<n;i++){
    while(cross(a[i],a[cur],b[(worst-1+m)%m])<cross(a[i],a[cur],b[worst])){
      // cerr<<"herea\n";
      worst=(worst-1+m)%m;
    }
    while(cross(a[i],a[cur],b[(worst+1)%m])<cross(a[i],a[cur],b[worst])){
      // cerr<<"hereb\n";
      worst=(worst+1)%m;
    }
    if(cross(a[i],a[cur],b[worst])<=0){
      // cerr<<cross(a[i],a[cur],b[worst])<<'\n';
      // cerr<<a[i].first<<' '<<a[i].second<<" to "<<a[cur].first<<' '<<a[cur].second<<'\n';
      area-=cross(a[i],a[(i+1)%n],a[cur]);
      continue;
    }//else cerr<<"fine "<<cross(a[i],a[cur],b[worst])<<'\n';
    while(1){
      area+=cross(a[i],a[cur],a[(cur+1)%n]);
      cur=(cur+1)%n;
      while(cross(a[i],a[cur],b[(worst-1+m)%m])<cross(a[i],a[cur],b[worst])){
        // cerr<<"here1\n";
        worst=(worst-1+m)%m;
      }
      while(cross(a[i],a[cur],b[(worst+1)%m])<cross(a[i],a[cur],b[worst])){
        // cerr<<"here2\n";
        worst=(worst+1)%m;
      }
      if(cross(a[i],a[cur],b[worst])<=0){
        // cerr<<cross(a[i],a[cur],b[worst])<<'\n';
        // cerr<<a[i].first<<' '<<a[i].second<<" to "<<a[cur].first<<' '<<a[cur].second<<'\n';
        area-=cross(a[i],a[(i+1)%n],a[cur]);
        break;
      }//else cerr<<"fine "<<cross(a[i],a[cur],b[worst])<<'\n';
      // cerr<<"setting "<<area<<' '<<i<<' '<<cur<<" :: "<<a[i]<<' '<<a[cur]<<'\n';
      maxi=max(maxi,area);
    }
  }
  cout<<maxi<<'\n';
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 39
• Subtask 3: 0 / 49