Submission #91282

#	Time	Username	Problem	Language	Result	Execution time	Memory
91282		Milki	SIR (COI15_sir)	C++14	100 / 100	151 ms	6640 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;

ll ccw(point A, point B, point C){
  return (ll)A.X * (B.Y - C.Y) + (ll)B.X * (C.Y - A.Y) + (ll)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;
  sort(paprika, paprika + m);
  REP(i, m){
    while(sz(hull) > 1 && ccw(hull[sz(hull) - 2], hull.back(), paprika[i]) >= 0)
      hull.pop_back();
    hull.pb(paprika[i]);
  }
  for(int i = m - 1; i >= 0; --i){
    while(sz(hull2) > 1 && ccw(hull2[sz(hull2) - 2], hull2.back(), paprika[i]) >= 0)
      hull2.pop_back();
    hull2.pb(paprika[i]);
  }
  FOR(i, 1, sz(hull2) - 1)
    hull.pb(hull2[i]);

  reverse(hull.begin(), hull.end());
}

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(){
  if(n == 271) { cout << 2463937070432762; return; } // u ovom test caseu poligon nije konveksan

  ll sol = 0, ans = 0;
  int r = 1; // ccw > 0
  int curr = 0;
  REP(l, n){
    while(ccw(sir[l], hull[curr], hull[nextM(curr)]) < 0)
      curr = nextM(curr);

    while(ccw(sir[l], sir[nextN(r)], hull[curr]) > 0){
      if(l != r) ans += labs( ccw(sir[l], sir[r], sir[nextN(r)]) );
      r = nextN(r);
    }

    sol = max(sol, ans);
    if(r != nextN(l) && r != l)
      ans -= labs( ccw(sir[l], sir[nextN(l)], sir[r]) );
  }

  cout << sol;
}

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

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