#778339 (C++14) No.2012 Largest Triangle

提出ソース

結果

問題	No.2012 Largest Triangle
ユーザー	👑 hos.lyric
提出日時	2022-07-15 21:45:01
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	109 ms / 2,500 ms
コード長	5,186 bytes
コンパイル時間	1,671 ms
コンパイル使用メモリ	112,992 KB
実行使用メモリ	17,068 KB
最終ジャッジ日時	2023-09-10 05:43:55
合計ジャッジ時間	5,601 ms
ジャッジサーバーID （参考情報）	judge12 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,380 KB
testcase_01	AC	2 ms 4,380 KB
testcase_02	AC	1 ms 4,380 KB
testcase_03	AC	2 ms 4,376 KB
testcase_04	AC	1 ms 4,380 KB
testcase_05	AC	1 ms 4,380 KB
testcase_06	AC	2 ms 4,380 KB
testcase_07	AC	1 ms 4,376 KB
testcase_08	AC	2 ms 4,376 KB
testcase_09	AC	1 ms 4,380 KB
testcase_10	AC	1 ms 4,380 KB
testcase_11	AC	2 ms 4,376 KB
testcase_12	AC	1 ms 4,380 KB
testcase_13	AC	2 ms 4,376 KB
testcase_14	AC	1 ms 4,380 KB
testcase_15	AC	2 ms 4,380 KB
testcase_16	AC	108 ms 16,184 KB
testcase_17	AC	106 ms 16,760 KB
testcase_18	AC	107 ms 15,784 KB
testcase_19	AC	108 ms 16,288 KB
testcase_20	AC	106 ms 15,504 KB
testcase_21	AC	108 ms 16,364 KB
testcase_22	AC	107 ms 16,380 KB
testcase_23	AC	107 ms 16,092 KB
testcase_24	AC	106 ms 15,956 KB
testcase_25	AC	106 ms 16,752 KB
testcase_26	AC	108 ms 16,068 KB
testcase_27	AC	108 ms 16,412 KB
testcase_28	AC	108 ms 15,964 KB
testcase_29	AC	108 ms 15,880 KB
testcase_30	AC	107 ms 17,068 KB
testcase_31	AC	109 ms 16,548 KB
testcase_32	AC	105 ms 16,516 KB
testcase_33	AC	109 ms 16,216 KB
testcase_34	AC	107 ms 15,752 KB
testcase_35	AC	109 ms 16,232 KB
testcase_36	AC	2 ms 4,380 KB
testcase_37	AC	2 ms 4,380 KB
testcase_38	AC	3 ms 4,380 KB
testcase_39	AC	2 ms 4,380 KB
testcase_40	AC	2 ms 4,380 KB
testcase_41	AC	25 ms 7,896 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// 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;
}

yukicoder

結果

テストケース

ソースコード