結果

問題 No.2355 Unhappy Back Dance
ユーザー KoDKoD
提出日時 2023-06-16 22:30:32
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3,053 ms / 6,000 ms
コード長 6,445 bytes
コンパイル時間 2,302 ms
コンパイル使用メモリ 154,212 KB
実行使用メモリ 319,872 KB
最終ジャッジ日時 2023-09-06 20:46:49
合計ジャッジ時間 38,980 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 124 ms
4,380 KB
testcase_07 AC 104 ms
4,380 KB
testcase_08 AC 126 ms
4,380 KB
testcase_09 AC 127 ms
4,376 KB
testcase_10 AC 1,090 ms
161,552 KB
testcase_11 AC 1,055 ms
161,792 KB
testcase_12 AC 146 ms
4,376 KB
testcase_13 AC 151 ms
4,376 KB
testcase_14 AC 1,096 ms
161,776 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 AC 3,053 ms
319,872 KB
testcase_17 AC 3,028 ms
319,652 KB
testcase_18 AC 2,966 ms
319,560 KB
testcase_19 AC 3,029 ms
319,592 KB
testcase_20 AC 2,935 ms
319,716 KB
testcase_21 AC 1,124 ms
135,276 KB
testcase_22 AC 153 ms
27,620 KB
testcase_23 AC 167 ms
29,428 KB
testcase_24 AC 2,704 ms
288,804 KB
testcase_25 AC 1,334 ms
157,060 KB
testcase_26 AC 1,387 ms
157,740 KB
testcase_27 AC 1,179 ms
137,812 KB
testcase_28 AC 12 ms
6,196 KB
testcase_29 AC 33 ms
10,452 KB
testcase_30 AC 2,406 ms
267,512 KB
testcase_31 AC 1,700 ms
195,744 KB
testcase_32 AC 106 ms
22,152 KB
testcase_33 AC 898 ms
112,712 KB
testcase_34 AC 5 ms
4,380 KB
testcase_35 AC 13 ms
6,468 KB
testcase_36 AC 1,112 ms
137,772 KB
testcase_37 AC 575 ms
74,984 KB
testcase_38 AC 734 ms
91,492 KB
testcase_39 AC 549 ms
72,576 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #define MULTEST

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <variant>
#include <vector>

namespace kod {
namespace util {

template <class F> class fixed_point : private F {
  constexpr fixed_point(F&& f) noexcept : F(std::forward<F>(f)) {}
  template <class G> friend constexpr decltype(auto) make_fixed(G&&) noexcept;

 public:
  template <class... Args> constexpr decltype(auto) operator()(Args&&... args) const noexcept {
    return F::operator()(*this, std::forward<Args>(args)...);
  }
};

template <class G> [[nodiscard]] constexpr decltype(auto) make_fixed(G&& g) noexcept {
  using F = std::decay_t<G>;
  return fixed_point<F>(std::forward<F>(g));
}

}  // namespace util
}  // namespace kod

namespace kod {
namespace util {

class forward_loop {
  int x, y;
  constexpr forward_loop(int x, int y) noexcept : x(x), y(y) {}
  friend constexpr forward_loop rep(int, int) noexcept;
  friend constexpr forward_loop rep(int) noexcept;

 public:
  constexpr forward_loop begin() const noexcept { return *this; }
  constexpr std::monostate end() const noexcept { return {}; }
  constexpr bool operator!=(std::monostate) const noexcept { return x < y; }
  constexpr void operator++() const noexcept {}
  constexpr int operator*() noexcept { return x++; }
};

[[nodiscard]] constexpr forward_loop rep(int l, int r) noexcept { return forward_loop(l, r); }
[[nodiscard]] constexpr forward_loop rep(int n) noexcept { return forward_loop(0, n); }

class backward_loop {
  int x, y;
  constexpr backward_loop(int x, int y) noexcept : x(x), y(y) {}
  friend constexpr backward_loop revrep(int, int) noexcept;
  friend constexpr backward_loop revrep(int) noexcept;

 public:
  constexpr backward_loop begin() const noexcept { return *this; }
  constexpr std::monostate end() const noexcept { return {}; }
  constexpr bool operator!=(std::monostate) const noexcept { return x > y; }
  constexpr void operator++() const noexcept {}
  constexpr int operator*() noexcept { return --x; }
};

[[nodiscard]] constexpr backward_loop revrep(int l, int r) noexcept { return backward_loop(r, l); }
[[nodiscard]] constexpr backward_loop revrep(int n) noexcept { return backward_loop(n, 0); }

template <class F> constexpr void repeat(int n, const F& f) noexcept {
  assert(n >= 0);
  while (n--) f();
}

}  // namespace util
}  // namespace kod

namespace kod {
namespace util {

namespace stdio_impl {

template <class T> T scan() {
  T x;
  std::cin >> x;
  return x;
}
struct scan_any {
  template <class T> operator T() const { return scan<T>(); }
};

}  // namespace stdio_impl

template <class T = void> decltype(auto) scan() {
  if constexpr (std::is_same_v<T, void>) return stdio_impl::scan_any{};
  else return stdio_impl::scan<T>();
}
template <class T, std::size_t N> std::array<T, N> scan_arr() {
  std::array<T, N> a;
  for (auto& x : a) x = scan<T>();
  return a;
}
template <class T> std::vector<T> scan_vec(int n) {
  if (n == -1) n = scan<int>();
  assert(n >= 0);
  std::vector<T> v;
  v.reserve(n);
  while (n--) v.push_back(scan<T>());
  return v;
}

void flush() { std::cout << std::flush; }
void print() {}
template <class T, class... Args> void print(const T& x, const Args&... args) {
  std::cout << x;
  if (sizeof...(args) != 0) std::cout << ' ';
  print(args...);
}
template <class... Args> void println(const Args&... args) {
  print(args...);
  std::cout << '\n';
}
template <class C> void print_seq(const C& c, const char* sep = " ", const char* end = "\n") {
  bool f = false;
  for (const auto& x : c) {
    if (f) std::cout << sep;
    else f = true;
    std::cout << x;
  }
  std::cout << end;
}

}  // namespace util
}  // namespace kod

namespace kod {
namespace sol {

using ll = long long;
using uint = unsigned;
using ull = unsigned long long;

using std::array;
using std::pair;
using std::string;
using std::tuple;
using std::vector;

using namespace util;

constexpr int inf = std::numeric_limits<int>::max() / 2;
constexpr ll infll = std::numeric_limits<ll>::max() / 2;

constexpr ll floor_div(ll x, ll y) noexcept {
  assert(y != 0);
  return x / y - ((x ^ y) < 0 && x % y != 0);
}
constexpr ll ceil_div(ll x, ll y) noexcept {
  assert(y != 0);
  return x / y + ((x ^ y) >= 0 && x % y != 0);
}

template <class T> constexpr bool setmin(T& lhs, const T& rhs) noexcept {
  if (lhs > rhs) {
    lhs = rhs;
    return true;
  }
  return false;
}
template <class T> constexpr bool setmax(T& lhs, const T& rhs) noexcept {
  if (lhs < rhs) {
    lhs = rhs;
    return true;
  }
  return false;
}

void run();

}  // namespace sol
}  // namespace kod

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout << std::fixed << std::setprecision(20);
  int cases = 1;
#ifdef MULTEST
  std::cin >> cases;
#endif
  while (cases--) kod::sol::run();
  return 0;
}

#ifdef KOD_LOCAL
#define OJ_LOCAL(a, b) b
#include <kodlib/misc/debug>
#else
#define OJ_LOCAL(a, b) a
#define DBG(...)
#define SHOW(...)
#endif

namespace kod {
namespace sol {

void run() {
  const int n = scan();
  vector<ll> x(n), y(n);
  for (const int i : rep(n)) {
    x[i] = scan();
    y[i] = scan();
  }
  std::map<tuple<ll, ll, __int128_t>, std::map<__int128_t, int>> map;
  for (const int i : rep(n)) {
    for (const int j : rep(i)) {
      ll a = x[j] - x[i];
      ll b = y[j] - y[i];
      ll g = std::gcd(a, b);
      a /= g, b /= g;
      ll c = (__int128_t)(-b) * x[i] + (__int128_t)(+a) * y[i];
      auto t1 = std::make_tuple(-b, +a, +c);
      auto t2 = std::make_tuple(+b, -a, -c);
      auto& v = map[std::min(t1, t2)];
      v[(__int128_t)a * x[i] + (__int128_t)b * y[i]] = i;
      v[(__int128_t)a * x[j] + (__int128_t)b * y[j]] = j;
    }
  }
  vector<int> ans(n);
  for (const auto& [t, m] : map) {
    int l = 0, r = (int)m.size();
    for (const auto& [v, i] : m) {
      r -= 1;
      if (l > 1 || r > 1) {
        ans[i] = 1;
      }
      l += 1;
    }
  }
  println(std::accumulate(ans.begin(), ans.end(), 0));
}

}  // namespace sol
}  // namespace kod
0