Submission #91276

#	Time	Username	Problem	Language	Result	Execution time	Memory
91276		Milki	SIR (COI15_sir)	C++14	0 / 100	163 ms	15208 KiB

sir

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

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define X first
#define Y second

typedef long long ll;
typedef pair<int, int> point;
typedef long double ld;

const int MAXN = 3e5 + 5;

ld ccw(point A, point B, point C){
  return A.X * (B.Y - C.Y) + B.X * (C.Y - A.Y) + C.X * (A.Y - B.Y);
}

int n, m;
point sir[MAXN], paprika[MAXN];
vector <point> hull;

void load(){
  ios_base::sync_with_stdio(false); cin.tie(0);
  cin >> n;
  REP(i, n)
    cin >> sir[i].X >> sir[i].Y;
  cin >> m;
  REP(i, m)
    cin >> paprika[i].X >> paprika[i].Y;
}

void buildHull(){
  vector <point> hull2;
  reverse(sir, sir + n);
  sort(paprika, paprika + m);
  REP(i, m){
    while(sz(hull2) > 1 && ccw(hull2[sz(hull2) - 2], hull2.back(), paprika[i]) >= 0)
      hull2.pop_back();
    hull2.pb(paprika[i]);
  }
  for(int i = m - 1; i >= 0; --i){
    while(sz(hull) > 1 && ccw(hull2[sz(hull) - 2], hull.back(), paprika[i]) >= 0)
      hull.pop_back();
    hull.pb(paprika[i]);
  }
  FOR(i, 1, sz(hull2) - 1)
    hull.pb(hull2[i]);
}

int nextN(int x){
  if(x == n - 1) return 0;
  return x + 1;
}

int nextM(int x){
  if(x == sz(hull) - 1) return 0;
  return x + 1;
}

void solve(){
  ll sol = 0, ans = 0;
  int r = 1; // ccw > 0
  int curr = 0;
  REP(l, n){
    //cout << "curr l je" _ l << "\n";
    while(ccw(sir[l], hull[curr], hull[nextM(curr)]) > 0)
      curr = nextM(curr);
    //cout << "curr tocka je" _ sir[l].X _ sir[l].Y << "\n";
    //cout << "hull je" _ hull[curr].X _ hull[curr].Y << "\n";
    //cout << l _ r _ nextN(r) << " ohohoho\n";
    //cout <<sir[l].X _ sir[l].Y _ hull[curr].X _ hull[curr].Y _ sir[nextN(r)].X _ sir[nextN(r)].Y << "\n";
    //cout << sir[l].X _ sir[l].Y _ hull[curr].X _ hull[curr].Y << "\n";
    while(ccw(sir[l], sir[nextN(r)], hull[curr]) < 0){
      if(l != r) ans += abs( ccw(sir[l], sir[r], sir[nextN(r)]) );
      r = nextN(r);
    }
    sol = max(sol, ans);
    if(l != r)
      ans -= abs( ccw(sir[l], sir[nextN(l)], sir[r]) );
  }

  cout << sol;
}

int main(){
  load();
  buildHull();
  solve();
}

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