oj.uz

Submission #783667

# Submission time Handle Problem Language Result Execution time Memory
783667 2023-07-15T08:03:09 Z BERNARB01 SIR (COI15_sir) C++17
0 / 100
 1000 ms 7892 KB 
#include <bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }

template <typename H, typename... T>
void debug_out(H h, T... t) {
  cerr << " " << to_string(h);
  debug_out(t...);
}

#ifdef B01
#define deb(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define deb(...)
#endif

struct point {
  long long x;
  long long y;

  point() : x(0), y(0) {}
  point(long long x_, long long y_) : x(x_), y(y_) {}

  inline point operator-(const point& o) const { return point(x - o.x, y - o.y); }

  inline bool operator<(const point& o) const {
    return (x < o.x || (x == o.x && y < o.y));
  }

  inline bool is_upper() const {
    return (y > 0 || (y == 0 && x > 0));
  }

  inline int cmp_polar(const point& o) const {
    bool a = is_upper();
    bool b = o.is_upper();
    if (a != b) {
      return (a ? -1 : 1);
    }
    long long v = x * o.y - y * o.x;
    return (v > 0 ? -1 : (v < 0 ? 1 : 0));
  }

  friend long long vmul(const point& a, const point& b) {
    return a.x * b.y - a.y * b.x;
  }
};

string to_string(point p) {
  return "(" + to_string(p.x) + ", " + to_string(p.y) + ")";
}

typedef vector<point> polygon;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  polygon p(n);
  for (int i = 0; i < n; i++) {
    cin >> p[i].x >> p[i].y;
  }
  int m;
  cin >> m;
  vector<point> pts(m);
  for (int i = 0; i < m; i++) {
    cin >> pts[i].x >> pts[i].y;
  }
  long long res = 0;
  for (int i = 0; i < n; i++) {
    point best = pts[0];
    for (int j = 0; j < m; j++) {
      if ((pts[j] - p[i]).cmp_polar(best - p[i]) <= 0) {
        best = pts[j];
      }
    }
    long long a2 = vmul(p[i], p[(i + 1) % n]);
    for (int j = 2; j < n; j++) {
      int br = (i + j - 1) % n;
      int r = (i + j) % n;
      if (vmul(p[r] - p[i], best - p[r]) <= 0) {
        break;
      }
      a2 += vmul(p[br], p[r]);
      res = max(res, llabs(a2 + vmul(p[r], p[i])));
    }
  }
  cout << res << '\n';
  return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1075 ms 7892 KB Time limit exceeded
2 Halted 0 ms 0 KB -