제출 #1271409

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271409		noyancanturk	SIR (COI15_sir)	C++20	100 / 100	134 ms	27060 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);
  assert(a.size()==n);
  n=a.size();
  m=b.size();
  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])<cross(a[i],a[cur],b[worst])){
      worst=(worst+1)%m;
    }
    if(cross(a[i],a[cur],b[worst])<=0){
      area-=cross(a[i],a[(i+1)%n],a[cur]);
      continue;
    }
    // cerr<<"ok "<<a[i]<<' '<<a[cur]<<"\n";
    maxi=max(maxi,area);
    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])<cross(a[i],a[cur],b[worst])){
        worst=(worst+1)%m;
      }
      if(cross(a[i],a[cur],b[worst])<=0){
        area-=cross(a[i],a[(i+1)%n],a[cur]);
        break;
      }
      // cerr<<"ok "<<a[i]<<' '<<a[cur]<<"\n"; 
      maxi=max(maxi,area);
    }
  }
  cout<<maxi<<'\n';
}

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