結果
| 問題 | No.2355 Unhappy Back Dance |
| ユーザー |
 KoD
|
| 提出日時 | 2023-06-16 22:30:32 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 3,048 ms / 6,000 ms |
| コード長 | 6,445 bytes |
| コンパイル時間 | 1,739 ms |
| コンパイル使用メモリ | 156,316 KB |
| 実行使用メモリ | 319,616 KB |
| 最終ジャッジ日時 | 2024-06-24 15:07:36 |
| 合計ジャッジ時間 | 36,930 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 37 |
ソースコード
// #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