Submission #783766

#	Time	Username	Problem	Language	Result	Execution time	Memory
783766		BERNARB01	SIR (COI15_sir)	C++17	0 / 100	1063 ms	7896 KiB

sir

#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
• Subtask 2: 0 / 39
• Subtask 3: 0 / 49