verify 追加 aoj2310 - Githubissues

提出: https://onlinejudge.u-aizu.ac.jp/beta/review.html#ACPC_2022_05_18/6666218
#include <bits/stdc++.h>
using namespace std;

// template {{{
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

#define  range(i, l, r) for (i64 i = (i64)(l); i < (i64)(r); (i) += 1)
#define rrange(i, l, r) for (i64 i = (i64)(r) - 1; i >= (i64)(l); (i) -= 1)

#define  whole(f, x, ...) ([&](decltype((x)) container) { return (f)(  begin(container),  end(container), ## __VA_ARGS__); })(x)
#define rwhole(f, x, ...) ([&](decltype((x)) container) { return (f)( rbegin(container), rend(container), ## __VA_ARGS__); })(x)

#define debug(x) cerr << "(" << __LINE__ << ")" << #x << ": " << (x) << endl

constexpr i32 inf   = 1001001001;
constexpr i64 infll = 1001001001001001001ll;

constexpr i32 dx[] = {0, -1, 1, 0, -1, 1, -1, 1}; 
constexpr i32 dy[] = {-1, 0, 0, 1, -1, -1, 1, 1};

struct IoSetup { IoSetup(i32 x = 15){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(x); cerr << fixed << setprecision(x); } } iosetup;

template <typename T = i64> T input() { T x; cin >> x; return x; }

template <typename T> ostream &operator<<(ostream &os, vector<T> &v) { range(i, 0, v.size()) { os << v[i] << (i + 1 != (int)v.size() ? " " : ""); } return os; } 
template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &in : v) is >> in; return is; }

template <typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }

template <typename T> vector<T> make_vector(size_t a, T b) { return vector<T>(a, b); }
template <typename... Ts> auto make_vector(size_t a, Ts... ts) { return vector<decltype(make_vector(ts...))>(a, make_vector(ts...)); }

template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
// }}}

#include "src/integer-geometry/point.hpp"
#include "src/integer-geometry/argcmp.hpp"
#include "src/integer-geometry/det.hpp"

void solve() {
  int h = input(), w = input();

  auto cs = make_vector(h + 2, w + 2, '.');
  range(i, 1, h + 1) range(j, 1, w + 1) {
    cin >> cs[i][j];
  }

  using point = intgeometry2d::lattice_point<i32>;
  vector< pair<point, int> > pts;
  rrange(i, 0, h + 1) range(j, 0, w + 1) {
    // cs[ i ][j] cs[ i ][j+1]
    // cs[i+1][j] cs[i+1][j+1]
    // centor: (h - i, j) ?
    auto is_dot = [](char c) {
      return '.' == c;
    };

    bool ul = is_dot(cs[i][j]);
    bool ur = is_dot(cs[i][j + 1]);
    bool dl = is_dot(cs[i + 1][j]);
    bool dr = is_dot(cs[i + 1][j + 1]);

    // split pattern:
    // #.    .#
    // .. or ##
    if ((ul != ur) and (ur == dl) and (dl == dr)) {
      pts.emplace_back(point(h - i, j), -1);
    }

    // merge pattern:
    // ..    ##
    // .# or #.
    if (ul == ur and ur == dl and dl != dr) {
      pts.emplace_back(point(h - i, j), 1);
    }
  }

  pts.emplace_back(point(-1, -1), 0);

  auto cmp = [](pair<point, int> &a, pair<point, int> &b) {
    return intgeometry2d::argcmp(a.first, b.first);
  };
  whole(sort, pts, cmp);

  int ans = 1;
  int cnt = 2;
  range(i, 1, pts.size()) {
    point pre = pts[i - 1].first;
    point pt = pts[i].first;
    if (intgeometry2d::det(pre, pt)) {
      chmax(ans, cnt);
    }

    cnt += pts[i].second;
  }

  cout << ans << endl;
}

signed main() {
  solve();
}
Luzhiled / comp-geometry

verify 追加 aoj2310 #46
