oj.uz

Submission #91282

# Submission time Handle Problem Language Result Execution time Memory
91282 2018-12-26T23:24:20 Z Milki SIR (COI15_sir) C++14
100 / 100
 151 ms 6640 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 572 KB Output is correct
3 Correct 2 ms 572 KB Output is correct
4 Correct 2 ms 572 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 584 KB Output is correct
2 Correct 10 ms 584 KB Output is correct
3 Correct 3 ms 732 KB Output is correct
4 Correct 2 ms 732 KB Output is correct
5 Correct 3 ms 732 KB Output is correct
6 Correct 3 ms 752 KB Output is correct

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 6172 KB Output is correct
2 Correct 149 ms 6172 KB Output is correct
3 Correct 127 ms 6640 KB Output is correct
4 Correct 41 ms 6640 KB Output is correct
5 Correct 124 ms 6640 KB Output is correct
6 Correct 119 ms 6640 KB Output is correct