結果

問題 No.2331 Maximum Quadrilateral
コンテスト
ユーザー tnakao0123
提出日時 2023-06-27 15:01:12
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,172 bytes
コンパイル時間 646 ms
コンパイル使用メモリ 61,464 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-04 07:56:43
合計ジャッジ時間 1,827 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 40 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 2331.cc:  No.2331 Maximum Quadrilateral - yukicoder
 */

#include<cstdio>
#include<vector>
#include<algorithm>
 
using namespace std;

/* constant */

/* typedef */

template <typename T>
struct Pt {
  T x, y;
  Pt() {}
  Pt(T _x, T _y) : x(_x), y(_y) {}
  Pt(const Pt<T> &p) : x(p.x), y(p.y) {}

  Pt<T> operator+(const Pt<T> p) const { return Pt<T>(x + p.x, y + p.y); }
  Pt<T> operator-() const { return Pt<T>(-x, -y); }
  Pt<T> operator-(const Pt<T> p) const { return Pt<T>(x - p.x, y - p.y); }
  Pt<T> operator*(T t) const { return Pt<T>(x * t, y * t); }
  Pt<T> operator/(T t) const { return Pt<T>(x / t, y / t); }
  T dot(Pt<T> v) const { return x * v.x + y * v.y; }
  T cross(Pt<T> v) const { return x * v.y - y * v.x; }
  Pt<T> mid(const Pt<T> p) { return Pt<T>((x + p.x) / 2, (y + p.y) / 2); }
  T d2() { return x * x + y * y; }
  double d() { return sqrt(d2()); }

  bool operator==(const Pt<T> pt) const { return x == pt.x && y == pt.y; }
  bool operator<(const Pt<T> &pt) const {
    return x < pt.x || (x == pt.x && y < pt.y);
  }
};

typedef Pt<int> pt;
typedef vector<pt> vpt;

/* global variables */

/* subroutines */

void convex_hull(const vpt& ps, vpt& chs) {
  int n = ps.size();
  vpt lhs, uhs;

  lhs.push_back(ps[0]);
  lhs.push_back(ps[1]);
  for (int i = 2; i < n; i++) {
    while (lhs.size() >= 2) {
      int ln = lhs.size();
      pt &lh0 = lhs[ln - 2], &lh1 = lhs[ln - 1];
      if ((lh1 - lh0).cross(ps[i] - lh1) > 0) break;
      lhs.pop_back();
    }
    lhs.push_back(ps[i]);
  }

  uhs.push_back(ps[n - 1]);
  uhs.push_back(ps[n - 2]);
  for (int i = n - 3; i >= 0; i--) {
    while (uhs.size() >= 2) {
      int un = uhs.size();
      pt &uh0 = uhs[un - 2], &uh1 = uhs[un - 1];
      if ((uh1 - uh0).cross(ps[i] - uh1) > 0) break;
      uhs.pop_back();
    }
    uhs.push_back(ps[i]);
  }

  lhs.pop_back();
  uhs.pop_back();

  chs.clear();
  chs.reserve(lhs.size() + uhs.size());
  chs.assign(lhs.begin(), lhs.end());
  chs.insert(chs.end(), uhs.begin(), uhs.end());
}

inline int area(pt &p0, pt &p1, pt &p2) {
  return abs((p1 - p0).cross(p2 - p0));
}

int tsearch(vpt &chs, int i, int j0, int l0, int r0) {
  int m = chs.size(), j = (i + j0) % m;

  while (l0 + 2 < r0) {
    int kk0 = (l0 * 2 + r0) / 3;
    int kk1 = (l0 + r0 * 2) / 3;
    int s0 = area(chs[i], chs[j], chs[(i + kk0) % m]);
    int s1 = area(chs[i], chs[j], chs[(i + kk1) % m]);
    if (s0 < s1) l0 = kk0;
    else r0 = kk1;
  }

  int maxs = 0;
  for (int k = l0; k <= r0; k++)
    maxs = max(maxs, area(chs[i], chs[j], chs[(i + k) % m]));

  return maxs;
}

/* main */

int main() {
  int n;
  scanf("%d", &n);
  vpt ps(n);
  for (int i = 0; i < n; i++) scanf("%d%d", &ps[i].x, &ps[i].y);
  sort(ps.begin(), ps.end());

  vpt chs;
  convex_hull(ps, chs);
  int m = chs.size();
  //printf("m=%d\n", m);
  //for (auto &p: chs) printf("%d, %d\n", p.x, p.y);

  int maxs = 0;
  for (int i = 0; i < m; i++) {
    for (int j0 = 2; j0 + 2 <= m; j0++) {
      int t0 = tsearch(chs, i, j0, 1, j0 - 1);
      int t1 = tsearch(chs, i, j0, j0 + 1, m - 1);
      maxs = max(maxs, t0 + t1);
    }
  }

  printf("%d\n", maxs);

  return 0;
}
0