oj.uz

Submission #91277

# Submission time Handle Problem Language Result Execution time Memory
91277 2018-12-26T22:36:44 Z Milki SIR (COI15_sir) C++14
61 / 100
 155 ms 20860 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(){
  ll sol = 0, ans = 0;
  int r = 1; // ccw > 0
  int curr = 0;
  REP(l, n){
    //cout << sir[l].X _ sir[l].Y _ hull[curr].X _ hull[curr].Y _ hull[nextM(curr)].X _ hull[nextM(curr)].Y << " ovo su hulovi \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 += abs( ccw(sir[l], sir[r], sir[nextN(r)]) );
      r = nextN(r);
    }
    //cout << sir[l].X _ sir[l].Y _ sir[r].X _ sir[r].Y _ hull[curr].X _ hull[curr].Y << "\n";

    sol = max(sol, ans);
    if(r != nextN(l) && r != l)
      ans -= abs( 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 376 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 728 KB Output is correct
2 Correct 3 ms 772 KB Output is correct
3 Correct 3 ms 848 KB Output is correct
4 Correct 2 ms 848 KB Output is correct
5 Incorrect 3 ms 988 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 6296 KB Output is correct
2 Correct 150 ms 7324 KB Output is correct
3 Correct 134 ms 8516 KB Output is correct
4 Correct 42 ms 8516 KB Output is correct
5 Correct 121 ms 14860 KB Output is correct
6 Correct 127 ms 20860 KB Output is correct