結果

問題 No.2012 Largest Triangle
ユーザー 👑 hos.lyrichos.lyric
提出日時 2022-07-15 21:45:01
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 110 ms / 2,500 ms
コード長 5,186 bytes
コンパイル時間 1,640 ms
コンパイル使用メモリ 116,164 KB
実行使用メモリ 15,944 KB
最終ジャッジ日時 2024-06-27 21:17:34
合計ジャッジ時間 5,603 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 109 ms
15,744 KB
testcase_17 AC 108 ms
15,752 KB
testcase_18 AC 108 ms
15,748 KB
testcase_19 AC 107 ms
15,748 KB
testcase_20 AC 109 ms
15,620 KB
testcase_21 AC 110 ms
15,620 KB
testcase_22 AC 108 ms
15,652 KB
testcase_23 AC 108 ms
15,744 KB
testcase_24 AC 107 ms
15,752 KB
testcase_25 AC 109 ms
15,616 KB
testcase_26 AC 107 ms
15,944 KB
testcase_27 AC 108 ms
15,916 KB
testcase_28 AC 109 ms
15,940 KB
testcase_29 AC 107 ms
15,804 KB
testcase_30 AC 108 ms
15,940 KB
testcase_31 AC 109 ms
15,664 KB
testcase_32 AC 107 ms
15,756 KB
testcase_33 AC 109 ms
15,628 KB
testcase_34 AC 107 ms
15,764 KB
testcase_35 AC 107 ms
15,760 KB
testcase_36 AC 2 ms
5,376 KB
testcase_37 AC 2 ms
5,376 KB
testcase_38 AC 3 ms
5,376 KB
testcase_39 AC 2 ms
5,376 KB
testcase_40 AC 2 ms
5,376 KB
testcase_41 AC 24 ms
7,760 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// https://onlinejudge.u-aizu.ac.jp/beta/room.html#TUPC2021/problems/K

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


struct Pt {
  Int x, y;
  Pt() {}
  Pt(Int x, Int y) : x(x), y(y) {}
  Pt operator+(const Pt &a) const { return Pt(x + a.x, y + a.y); }
  Pt operator-(const Pt &a) const { return Pt(x - a.x, y - a.y); }
  Pt operator*(const Pt &a) const { return Pt(x * a.x - y * a.y, x * a.y + y * a.x); }
  Pt operator+() const { return Pt(+x, +y); }
  Pt operator-() const { return Pt(-x, -y); }
  Pt operator*(const Int &k) const { return Pt(x * k, y * k); }
  Pt operator/(const Int &k) const { return Pt(x / k, y / k); }
  friend Pt operator*(const Int &k, const Pt &a) { return Pt(k * a.x, k * a.y); }
  Pt &operator+=(const Pt &a) { x += a.x; y += a.y; return *this; }
  Pt &operator-=(const Pt &a) { x -= a.x; y -= a.y; return *this; }
  Pt &operator*=(const Pt &a) { return *this = *this * a; }
  Pt &operator*=(const Int &k) { x *= k; y *= k; return *this; }
  Int abs2() const { return x * x + y * y; }
  Int dot(const Pt &a) const { return x * a.x + y * a.y; }
  Int det(const Pt &a) const { return x * a.y - y * a.x; }
  friend ostream &operator<<(ostream &os, const Pt &a) { os << "(" << a.x << ", " << a.y << ")"; return os; }
};
constexpr Int EPS = 0;
int sig(Int r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
Int tri(const Pt &a, const Pt &b, const Pt &c) { return (b - a).det(c - a); }

bool iSSStrict(const Pt &a, const Pt &b, const Pt &c, const Pt &d) {
  return (sig(tri(a, b, c)) * sig(tri(a, b, d)) < 0 && sig(tri(c, d, a)) * sig(tri(c, d, b)) < 0);
}

vector<Pt> convexHull(vector<Pt> ps) {
  const int n = ps.size();
  sort(ps.begin(), ps.end(), [&](const Pt &a, const Pt &b) {
    return ((a.x != b.x) ? (a.x < b.x) : (a.y < b.y));
  });
  vector<Pt> qs;
  for (int i = 0; i < n; qs.push_back(ps[i++]))
    for (; qs.size() > 1 && sig(tri(qs[qs.size() - 2], qs[qs.size() - 1], ps[i])) <= 0; qs.pop_back()) {}
  const size_t r = qs.size();
  for (int i = (int)ps.size() - 2; i >= 0; qs.push_back(ps[i--]))
    for (; qs.size() > r && sig(tri(qs[qs.size() - 2], qs[qs.size() - 1], ps[i])) <= 0; qs.pop_back()) {}
  qs.pop_back();
  return qs;
}


int N;
// vector<Int> A;
vector<Pt> P;

int main() {
  for (; ~scanf("%d", &N); ) {
    // A.resize(N);
    // for (int u = 0; u < N; ++u) {
      // scanf("%lld", &A[u]);
    // }
    P.resize(N);
    for (int u = 0; u < N; ++u) {
      scanf("%lld%lld", &P[u].x, &P[u].y);
    }
    
    // for (int u = 0; u < N; ++u) {
      // vector<Pt> ps;
      // for (int v = 0; v < N; ++v) if (u != v) {
        // ps.push_back(A[v] * (P[v] - P[u]));
      // }
#define ps P
      const auto qs = convexHull(ps);
      vector<pair<Pt, int>> es;
      for (const Pt &p : ps) {
        es.emplace_back(p, 1);
      }
      es.emplace_back(Pt(+1, 0), 0);
      es.emplace_back(Pt(0, +1), 0);
      es.emplace_back(Pt(-1, 0), 0);
      es.emplace_back(Pt(0, -1), 0);
      sort(es.begin(), es.end(), [&](const pair<Pt, int> &a_, const pair<Pt, int> &b_) {
        const Pt &a = a_.first;
        const Pt &b = b_.first;
        const int sa = (a.y > 0) ? 1 : (a.y < 0) ? 3 : (a.x > 0) ? 0 : 2;
        const int sb = (b.y > 0) ? 1 : (b.y < 0) ? 3 : (b.x > 0) ? 0 : 2;
        return ((sa != sb) ? (sa < sb) : (a.det(b) > 0));
      });
      const int esLen = es.size();
      const int qsLen = qs.size();
// cerr<<"es = ";pv(es.begin(),es.end());
// cerr<<"qs = ";pv(qs.begin(),qs.end());
      Int ans = 0;
      {
        int k = 0;
        for (int h = 0; h < 2; ++h) for (int j = 0; j < esLen; ++j) {
          for (; ; ) {
            int kk = k + 1;
            if (kk >= qsLen) kk -= qsLen;
            if (es[j].first.det(qs[kk] - qs[k]) > 0) {
              k = kk;
            } else {
              break;
            }
          }
// cerr<<"  "<<j<<" "<<k<<endl;
          if (es[j].second) {
            chmax(ans, es[j].first.det(qs[k]));
          }
        }
      }
      // ans *= A[u];
      printf("%lld\n", ans);

#ifdef LOCAL
Int brt=0;
// for(int v=0;v<N;++v)for(int w=0;w<N;++w)chmax(brt,A[u]*A[v]*A[w]*tri(P[u],P[v],P[w]));
for(int v=0;v<N;++v)for(int w=0;w<N;++w)chmax(brt,abs(P[v].det(P[w])));
cerr<<"brt = "<<brt<<endl;
assert(brt==ans);
#endif
    // }
#ifdef LOCAL
cerr<<"========"<<endl;
#endif
  }
  return 0;
}
0