oj.uz

Submission #783766

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

using namespace std;

#ifdef B01
#include "../deb.h"
#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); }

  long long abs2() const {
    return x * x + y * y;
  }

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

  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 : (abs2() < o.abs2() ? -1 : 1)));
  }
};

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;
  }
  sort(pts.begin(), pts.end(), [&](const point& i, const point& j) {
    return (i - p[0]).cmp_polar(j - p[0]) < 0;
  });
  long long res = 0;
  int z = 0;
  for (int i = 0; i < n; i++) {
    point best = pts[z];
    for (int j = 1; j < m; j++) {
      long long v = vmul(best - p[i], pts[(z + j) % m] - best);
      if (v <= 0) {
        best = pts[(z + j) % m];
      } else {
        z = (z + j - 1) % m;
        break;
      }
    }
    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 17 ms 360 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 1063 ms 7896 KB Time limit exceeded
2 Halted 0 ms 0 KB -