結果
| 問題 | No.2769 Number of Rhombi |
| ユーザー |
 iiljj
|
| 提出日時 | 2024-06-03 18:55:23 |
| 言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 1,494 ms / 5,000 ms |
| コード長 | 26,272 bytes |
| コンパイル時間 | 2,963 ms |
| コンパイル使用メモリ | 185,624 KB |
| 実行使用メモリ | 42,496 KB |
| 最終ジャッジ日時 | 2024-06-03 18:56:11 |
| 合計ジャッジ時間 | 38,193 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,812 KB |
| testcase_01 | AC | 2 ms
6,940 KB |
| testcase_02 | AC | 1 ms
6,940 KB |
| testcase_03 | AC | 1,070 ms
33,152 KB |
| testcase_04 | AC | 1,078 ms
30,976 KB |
| testcase_05 | AC | 802 ms
22,400 KB |
| testcase_06 | AC | 1,085 ms
27,648 KB |
| testcase_07 | AC | 1,404 ms
33,408 KB |
| testcase_08 | AC | 1,417 ms
34,176 KB |
| testcase_09 | AC | 1,439 ms
35,712 KB |
| testcase_10 | AC | 1,468 ms
37,888 KB |
| testcase_11 | AC | 1,475 ms
39,680 KB |
| testcase_12 | AC | 1,462 ms
41,088 KB |
| testcase_13 | AC | 1,494 ms
41,856 KB |
| testcase_14 | AC | 1,196 ms
42,240 KB |
| testcase_15 | AC | 1,085 ms
42,240 KB |
| testcase_16 | AC | 999 ms
42,368 KB |
| testcase_17 | AC | 881 ms
42,368 KB |
| testcase_18 | AC | 776 ms
42,368 KB |
| testcase_19 | AC | 716 ms
42,496 KB |
| testcase_20 | AC | 728 ms
42,496 KB |
| testcase_21 | AC | 658 ms
42,368 KB |
| testcase_22 | AC | 626 ms
42,368 KB |
| testcase_23 | AC | 601 ms
42,496 KB |
| testcase_24 | AC | 2 ms
6,948 KB |
| testcase_25 | AC | 1,310 ms
41,728 KB |
| testcase_26 | AC | 1,198 ms
42,112 KB |
| testcase_27 | AC | 867 ms
42,368 KB |
| testcase_28 | AC | 1,027 ms
42,368 KB |
| testcase_29 | AC | 706 ms
42,496 KB |
| testcase_30 | AC | 953 ms
42,368 KB |
| testcase_31 | AC | 1,385 ms
40,960 KB |
| testcase_32 | AC | 1,405 ms
34,048 KB |
| testcase_33 | AC | 1,385 ms
33,920 KB |
| testcase_34 | AC | 1,453 ms
37,120 KB |
ソースコード
/* #region Head */
// #include <bits/stdc++.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert> // assert.h
#include <cmath> // math.h
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pll = pair<ll, ll>;
template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;
using vll = vc<ll>;
using vvll = vvc<ll>;
using vld = vc<ld>;
using vvld = vvc<ld>;
using vs = vc<string>;
using vvs = vvc<string>;
template <class T, class U> using um = unordered_map<T, U>;
template <class T> using pq = priority_queue<T>;
template <class T> using pqa = priority_queue<T, vc<T>, greater<T>>;
template <class T> using us = unordered_set<T>;
#define TREP(T, i, m, n) for (T i = (m), i##_len = (T)(n); i < i##_len; ++(i))
#define TREPM(T, i, m, n) for (T i = (m), i##_max = (T)(n); i <= i##_max; ++(i))
#define TREPR(T, i, m, n) for (T i = (m), i##_min = (T)(n); i >= i##_min; --(i))
#define TREPD(T, i, m, n, d) for (T i = (m), i##_len = (T)(n); i < i##_len; i += (d))
#define TREPMD(T, i, m, n, d) for (T i = (m), i##_max = (T)(n); i <= i##_max; i += (d))
#define REP(i, m, n) for (ll i = (m), i##_len = (ll)(n); i < i##_len; ++(i))
#define REPM(i, m, n) for (ll i = (m), i##_max = (ll)(n); i <= i##_max; ++(i))
#define REPR(i, m, n) for (ll i = (m), i##_min = (ll)(n); i >= i##_min; --(i))
#define REPD(i, m, n, d) for (ll i = (m), i##_len = (ll)(n); i < i##_len; i += (d))
#define REPMD(i, m, n, d) for (ll i = (m), i##_max = (ll)(n); i <= i##_max; i += (d))
#define REPI(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)
#define REPIR(itr, ds) for (auto itr = ds.rbegin(); itr != ds.rend(); itr++)
#define ALL(x) begin(x), end(x)
#define SIZE(x) ((ll)(x).size())
#define ISIZE(x) ((int)(x).size())
#define PERM(c) \
sort(ALL(c)); \
for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))
#define UNIQ(v) v.erase(unique(ALL(v)), v.end());
#define CEIL(a, b) (((a) + (b)-1) / (b))
#define endl '\n'
constexpr ll INF = 1'010'000'000'000'000'017LL;
constexpr int IINF = 1'000'000'007LL;
constexpr ll MOD = 1'000'000'007LL; // 1e9 + 7
// constexpr ll MOD = 998244353;
constexpr ld EPS = 1e-12;
constexpr ld PI = 3.14159265358979323846;
// 前方宣言
template <typename T> istream &operator>>(istream &is, vc<T> &vec);
template <typename T> ostream &operator<<(ostream &os, const vc<T> &vec);
template <typename T> ostream &operator>>(ostream &os, const vc<T> &vec);
template <typename T, size_t _Nm> istream &operator>>(istream &is, array<T, _Nm> &arr);
template <typename T, size_t _Nm> ostream &operator<<(ostream &os, const array<T, _Nm> &arr);
template <typename T, size_t _Nm> ostream &operator>>(ostream &os, const array<T, _Nm> &arr);
template <typename T, typename U> istream &operator>>(istream &is, pair<T, U> &pair_var);
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &pair_var);
template <class T> ostream &out_iter(ostream &os, const T &map_var);
template <typename T, typename U> ostream &operator<<(ostream &os, const map<T, U> &map_var);
template <typename T, typename U> ostream &operator<<(ostream &os, const um<T, U> &map_var);
template <typename T> ostream &operator<<(ostream &os, const set<T> &set_var);
template <typename T> ostream &operator<<(ostream &os, const us<T> &set_var);
template <typename T> ostream &operator<<(ostream &os, const pq<T> &pq_var);
template <typename T> ostream &operator<<(ostream &os, const queue<T> &queue_var);
template <typename T> ostream &operator<<(ostream &os, const stack<T> &stk_var);
template <typename T> istream &operator>>(istream &is, vc<T> &vec) { // vector 入力
for (T &x : vec)
is >> x;
return is;
}
template <typename T> ostream &operator<<(ostream &os, const vc<T> &vec) { // vector 出力 (for dump)
os << "{";
REP(i, 0, SIZE(vec)) os << vec[i] << (i == i_len - 1 ? "" : ", ");
os << "}";
return os;
}
template <typename T> ostream &operator>>(ostream &os, const vc<T> &vec) { // vector 出力 (inline)
REP(i, 0, SIZE(vec)) os << vec[i] << (i == i_len - 1 ? "\n" : " ");
return os;
}
template <typename T, size_t _Nm> istream &operator>>(istream &is, array<T, _Nm> &arr) { // array 入力
REP(i, 0, SIZE(arr)) is >> arr[i];
return is;
}
template <typename T, size_t _Nm> ostream &operator<<(ostream &os, const array<T, _Nm> &arr) { // array 出力 (for dump)
os << "{";
REP(i, 0, SIZE(arr)) os << arr[i] << (i == i_len - 1 ? "" : ", ");
os << "}";
return os;
}
template <typename T, typename U> istream &operator>>(istream &is, pair<T, U> &pair_var) { // pair 入力
is >> pair_var.first >> pair_var.second;
return is;
}
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &pair_var) { // pair 出力
os << "(" << pair_var.first << ", " << pair_var.second << ")";
return os;
}
// map, um, set, us 出力
template <class T> ostream &out_iter(ostream &os, const T &map_var) {
os << "{";
REPI(itr, map_var) {
os << *itr;
auto itrcp = itr;
if (++itrcp != map_var.end()) os << ", ";
}
return os << "}";
}
template <typename T, typename U> ostream &operator<<(ostream &os, const map<T, U> &map_var) {
return out_iter(os, map_var);
}
template <typename T, typename U> ostream &operator<<(ostream &os, const um<T, U> &map_var) {
os << "{";
REPI(itr, map_var) {
auto [key, value] = *itr;
os << "(" << key << ", " << value << ")";
auto itrcp = itr;
if (++itrcp != map_var.end()) os << ", ";
}
os << "}";
return os;
}
template <typename T> ostream &operator<<(ostream &os, const set<T> &set_var) { return out_iter(os, set_var); }
template <typename T> ostream &operator<<(ostream &os, const us<T> &set_var) { return out_iter(os, set_var); }
template <typename T> ostream &operator<<(ostream &os, const pq<T> &pq_var) {
pq<T> pq_cp(pq_var);
os << "{";
if (!pq_cp.empty()) {
os << pq_cp.top(), pq_cp.pop();
while (!pq_cp.empty())
os << ", " << pq_cp.top(), pq_cp.pop();
}
return os << "}";
}
// tuple 出力
template <size_t N = 0, bool end_line = false, typename... Args> ostream &operator<<(ostream &os, tuple<Args...> &a) {
if constexpr (N < std::tuple_size_v<tuple<Args...>>) {
os << get<N>(a);
if constexpr (N + 1 < std::tuple_size_v<tuple<Args...>>) {
os << ' ';
} else if constexpr (end_line) {
os << '\n';
}
return operator<< <N + 1, end_line>(os, a);
}
return os;
}
template <typename... Args> void print_tuple(tuple<Args...> &a) { operator<< <0, true>(std::cout, a); }
void pprint() { std::cout << endl; }
template <class Head, class... Tail> void pprint(Head &&head, Tail &&...tail) {
std::cout << head;
if (sizeof...(Tail) > 0) std::cout << ' ';
pprint(move(tail)...);
}
// dump
#define DUMPOUT cerr
void dump_func() { DUMPOUT << endl; }
template <class Head, class... Tail> void dump_func(Head &&head, Tail &&...tail) {
DUMPOUT << head;
if (sizeof...(Tail) > 0) DUMPOUT << ", ";
dump_func(move(tail)...);
}
// chmax (更新「される」かもしれない値が前)
template <typename T, typename U, typename Comp = less<>> bool chmax(T &xmax, const U &x, Comp comp = {}) {
if (comp(xmax, x)) {
xmax = x;
return true;
}
return false;
}
// chmin (更新「される」かもしれない値が前)
template <typename T, typename U, typename Comp = less<>> bool chmin(T &xmin, const U &x, Comp comp = {}) {
if (comp(x, xmin)) {
xmin = x;
return true;
}
return false;
}
// ローカル用
#ifndef ONLINE_JUDGE
#define DEBUG_
#endif
#ifndef MYLOCAL
#undef DEBUG_
#endif
#ifdef DEBUG_
#define DEB
#define dump(...) \
DUMPOUT << " " << string(#__VA_ARGS__) << ": " \
<< "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" << endl \
<< " ", \
dump_func(__VA_ARGS__)
#else
#define DEB if (false)
#define dump(...)
#endif
#define VAR(type, ...) \
type __VA_ARGS__; \
assert((std::cin >> __VA_ARGS__));
template <typename T> istream &operator,(istream &is, T &rhs) { return is >> rhs; }
template <typename T> ostream &operator,(ostream &os, const T &rhs) { return os << ' ' << rhs; }
struct AtCoderInitialize {
static constexpr int IOS_PREC = 15;
static constexpr bool AUTOFLUSH = false;
AtCoderInitialize() {
ios_base::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
std::cout << fixed << setprecision(IOS_PREC);
if (AUTOFLUSH) std::cout << unitbuf;
}
} ATCODER_INITIALIZE;
void Yn(bool p) { std::cout << (p ? "Yes" : "No") << endl; }
void YN(bool p) { std::cout << (p ? "YES" : "NO") << endl; }
template <typename T> constexpr void operator--(vc<T> &v, int) noexcept {
for (int i = 0; i < ISIZE(v); ++i)
v[i]--;
}
template <typename T> constexpr void operator++(vc<T> &v, int) noexcept {
for (int i = 0; i < ISIZE(v); ++i)
v[i]++;
}
/* #endregion */
// #include <atcoder/all>
// using namespace atcoder;
/* #region Rational */
template <typename T> struct RationalNum {
// 分子
T numerator;
// 分母
T denominator;
RationalNum() { numerator = 0, denominator = 1; }
// RationalNum(double x);
RationalNum(T numerator_, T denominator_ = 1) {
numerator = numerator_, denominator = denominator_;
simplify();
}
// 自身を簡約する
void simplify() { RationalNum<T>::simplifyNums(numerator, denominator); }
static T mygcd(const T &a, const T &b) {
// std::gcd が使える場合
if constexpr ((std::is_integral<T>::value)) {
return std::gcd(a, b);
}
// std::gcd が使えない場合 (__int128_t など)
if (b == 0) {
return a;
} else {
return mygcd(b, a % b);
}
}
static void simplifyNums(T &numerator_, T &denominator_) {
if (denominator_ == 0) { // 分母が 0 のときの正規化
if (numerator_ > 0) numerator_ = 1; // 無限大
else if (numerator_ < 0)
numerator_ = -1; // 無限小
else
numerator_ = 0; // 不定
} else {
T g = mygcd(numerator_, denominator_);
numerator_ /= g, denominator_ /= g;
if (denominator_ < 0) numerator_ *= -1, denominator_ *= -1;
}
}
// 逆数を返す．
RationalNum<T> inv() const { return RationalNum<T>(denominator, numerator); }
// t 乗を返す．
RationalNum<T> pow(ll t) const {
RationalNum<T> a(*this);
RationalNum<T> res = T(1);
while (t) {
if (t & 1) res *= a;
t >>= 1;
if (t == 0) break;
a *= a;
}
return res;
}
// 小数点以下を切り上げた整数を返す
T ceil() const {
if (numerator >= 0) return (numerator + denominator - 1) / denominator;
else
return numerator / denominator;
}
// 小数点以下を切り捨てた整数を返す
T floor() const {
if (numerator >= 0) return numerator / denominator;
else
return (numerator - denominator + 1) / denominator;
}
// 正の無限大かどうかを返す
bool is_infinity() const { return numerator == 1 and denominator == 0; }
// 負の無限大かどうかを返す
bool is_munus_infinity() const { return numerator == -1 and denominator == 0; }
// 不定かどうか返す
bool is_indeterminate() const { return numerator == 0 and denominator == 0; }
// operator ll() const { return floor(); }
// member function
RationalNum<T> &operator+=(const RationalNum<T> &obj) { return *this = *this + obj; }
RationalNum<T> &operator-=(const RationalNum<T> &obj) { return *this = *this - obj; }
RationalNum<T> &operator*=(const RationalNum<T> &obj) { return *this = *this * obj; }
RationalNum<T> &operator/=(const RationalNum<T> &obj) { return *this = *this / obj; }
RationalNum<T> &operator++() { return *this = *this + 1; }
RationalNum<T> operator++(int) {
RationalNum<T> before = *this;
*this = *this + 1;
return before;
}
RationalNum<T> &operator--() { return *this = *this - 1; }
RationalNum<T> operator--(int) {
RationalNum<T> before = *this;
*this = *this - 1;
return before;
}
RationalNum<T> operator+() const { return *this; }
RationalNum<T> operator-() const { return RationalNum<T>(-numerator, denominator); }
// friend functions
friend RationalNum<T> operator+(const RationalNum<T> &left, const RationalNum<T> &right) {
if (left.denominator == 0 && right.denominator == 0) {
if (left.numerator == 0) return left; // left が不定
if (right.numerator == 0) return right; // right が不定
if ((left > T(0) && right > T(0)) || (left < T(0) && right < T(0))) {
return left; // 無限大・無限小
} else {
return RationalNum<T>(0, 0); // 不定
}
} else if (left.denominator == 0) {
return left;
} else if (right.denominator == 0) {
return right;
}
RationalNum<T> temp;
T tempLD = left.denominator;
T tempRD = right.denominator;
RationalNum<T>::simplifyNums(tempLD, tempRD);
temp.denominator = left.denominator * tempRD;
temp.numerator = left.numerator * tempRD + right.numerator * tempLD;
temp.simplify();
return temp;
}
friend RationalNum<T> operator-(const RationalNum<T> &left, const RationalNum<T> &right) {
return left + (-right); //
}
friend RationalNum<T> operator*(const RationalNum<T> &left, const RationalNum<T> &right) {
T a = left.denominator, b = right.numerator, c = right.denominator, d = left.numerator;
RationalNum<T>::simplifyNums(b, a), RationalNum<T>::simplifyNums(d, c);
return RationalNum<T>(b * d, a * c);
}
friend RationalNum<T> operator/(const RationalNum<T> &left, const RationalNum<T> &right) {
return left * right.inv(); //
}
friend bool operator==(const RationalNum<T> &left, const RationalNum<T> &right) {
return (left.numerator == right.numerator && left.denominator == right.denominator);
}
friend bool operator!=(const RationalNum<T> &left, const RationalNum<T> &right) {
return !(left == right); //
}
friend bool operator<(const RationalNum<T> &left, const RationalNum<T> &right) {
// RationalNum<T> indeterminate(0, 0);
if (left.is_indeterminate() or right.is_indeterminate()) {
// どちらかが不定のときは大小を正しく計算できないので，特別扱いする
// 便宜上，不定は「無限大より大きい」として扱う
if (not right.is_indeterminate()) {
return false;
} else if (not left.is_indeterminate()) {
return true;
} else {
return false;
}
}
// 符号が異なるときはすぐ判定できる
if (left.numerator < 0 && right.numerator >= 0) return true;
if (left.numerator <= 0 && right.numerator > 0) return true;
if (left.numerator > 0 && right.numerator <= 0) return false;
if (left.numerator >= 0 && right.numerator < 0) return false;
// 両方 0 の場合
if (left.numerator == 0 && right.numerator == 0) return false;
// 分母が等しい場合
if (left.denominator == right.denominator) {
return left.numerator < right.numerator;
}
// 分子が等しい場合（通分しないで済むなら嬉しいので）（若干高速化できる）
if (left.numerator == right.numerator) {
if (left.numerator > 0) {
// 正の数→分母が大きいほど分数としては小さい
return left.denominator > right.denominator;
} else {
// 負の数→分母が大きいほど分数としても大きい
return left.denominator < right.denominator;
}
}
// どちらかが正・負の無限大の場合
if (left.is_infinity()) {
// right は不定でないことは確定しているので，left を超えることはない
return false;
} else if (left.is_munus_infinity()) {
// right が -inf でないなら，right のほうが大きい
return not right.is_munus_infinity();
} else if (right.is_infinity()) {
// left が inf でないなら，right のほうが大きい
return not left.is_infinity();
} else if (right.is_munus_infinity()) {
// left は不定ではないことは確定しているので， right を下回ることはない
// また left は -inf ではないことは確定しているので，left > right である
return false;
}
// 整数に丸めて比較可能ならそうする（若干高速化できる）
if (left.numerator > 0) {
assert(right.numerator > 0);
const T q_left = left.floor();
const T q_right = right.floor();
if (q_left != q_right) {
return q_left < q_right;
}
} else {
assert(left.numerator < 0);
assert(right.numerator < 0);
const T q_left = left.ceil();
const T q_right = right.ceil();
if (q_left != q_right) {
return q_left < q_right;
}
}
// ジャッジサーバでは __int128_t でも is_integral == true になるので，
// この分岐は使わない
// if constexpr ((std::is_integral<T>::value)) {
// ll lside;
// bool of0 = __builtin_mul_overflow(left.numerator, right.denominator, &lside);
// // = left.numerator * right.denominator;
// ll rside;
// bool of1 = __builtin_mul_overflow(left.denominator, right.numerator, &rside);
// // left.denominator * right.numerator;
// if (!of0 && !of1) return (lside < rside); // 両方ok
// __int128_t lside128 = __int128_t(left.numerator) * right.denominator;
// __int128_t rside128 = __int128_t(left.denominator) * right.numerator;
// return (lside128 < rside128);
// }
RationalNum<T> diff = right - left;
return diff.numerator > 0;
}
// // 積が ll を超えることもあるので，map のキーで使うとかのときは，
// // 異なる RationalNum の間に必ず大小関係が定義できる（ただし分数の大小とは異なる）こちらを使う?
// friend bool operator<(const RationalNum &left, const RationalNum &right) {
// return left.numerator == right.numerator ? left.denominator < right.denominator : left.numerator <
// right.numerator;
// }
friend bool operator>(const RationalNum<T> &left, const RationalNum<T> &right) {
// ll lside = left.getNumerator() * right.getDenominator();
// ll rside = left.getDenominator() * right.getNumerator();
// return (lside > rside);
return !(left < right) && (left != right);
}
friend bool operator<=(const RationalNum<T> &left, const RationalNum<T> &right) {
return ((left < right) || (left == right));
}
friend bool operator>=(const RationalNum<T> &left, const RationalNum<T> &right) {
return ((left > right) || (left == right));
}
// 出力
friend ostream &operator<<(ostream &out, const RationalNum<T> &obj) {
if (obj.denominator == 0) {
if (obj.numerator > 0) out << "inf";
else if (obj.numerator < 0)
out << "-inf";
else
out << "indeterminate";
} else {
out << obj.numerator;
if (obj.numerator != 0 && obj.denominator != 1) out << "/" << obj.denominator;
}
return out;
}
// 小数の入力には使っても問題なさそう
// https://atcoder.jp/contests/abc169/tasks/abc169_c
// 入力
friend istream &operator>>(istream &in, RationalNum<T> &obj) {
string inputstr;
T num = 0;
int sign = 1;
bool slashExist = false;
bool dotExist = false;
// bool validInput = true;
T virtualDenominator = 1;
cin >> inputstr;
REP(i, 0, SIZE(inputstr)) {
char temp = inputstr[i];
if (temp == '.') {
if (dotExist == false && slashExist == false && i != 0) {
dotExist = true;
}
// else {
// validInput = false;
// break;
// }
} else if (temp == '/') {
if (dotExist == false && slashExist == false && i != 0) {
slashExist = true;
obj.numerator = (sign * num);
num = 0;
sign = 1;
}
// else {
// validInput = false;
// break;
// }
} else if (temp == '-') {
if (i == 0) {
sign = -sign;
} else if (inputstr[i - 1] == '/') {
sign = -sign;
}
// else {
// validInput = false;
// break;
// }
} else if (temp <= '9' && temp >= '0') {
if (dotExist) {
// if (virtualDenominator > INF / 10) {
// cerr << "this frational is too long to handle.";
// validInput = false;
// break;
// } else
virtualDenominator *= 10;
}
// if (num > INF / 10) {
// cerr << "this number is too long to handle.";
// validInput = false;
// break;
// }
num *= 10;
num += inputstr[i] - '0';
}
// else {
// validInput = false;
// break;
// }
}
// if (validInput == false) {
// obj.numerator = (0);
// obj.denominator = (1);
// cerr << "Input is not valid! The whole set to 0" << endl;
// }
if (slashExist == true) {
obj.denominator = (sign * num);
} else if (dotExist) {
obj.numerator = (sign * num);
obj.denominator = (virtualDenominator);
} else {
obj.numerator = (sign * num);
obj.denominator = (1);
}
obj.simplify();
return in;
}
};
// __int128_t を使わない場合はアンコメントする
// template <typename T> void hash_combine(size_t &seed, T const &v) {
// // 基本型に関するハッシュ生成は標準ライブラリが提供している
// std::hash<T> primitive_type_hash;
// // 生成したハッシュを合成する。このコードはboostものを使用する
// seed ^= primitive_type_hash(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
// }
template <typename T> struct std::hash<RationalNum<T>> {
public:
// クラスのメンバの値それぞれについてハッシュ生成して、それらを結合して一つのハッシュ値にする
size_t operator()(const RationalNum<T> &data) const {
std::size_t seed = 0;
hash_combine(seed, data.numerator);
hash_combine(seed, data.denominator);
return seed;
}
};
/* #endregion */
// Problem
void solve() {
VAR(ll, n);
vll x(n), y(n);
REP(i, 0, n) cin >> x[i], y[i];
using R = RationalNum<ll>;
// 中点の座標と傾きを記録する
map<pair<pll, R>, ll> mp;
REP(i, 0, n - 1) REP(j, i + 1, n) {
const ll xx = x[i] + x[j];
const ll yy = y[i] + y[j];
const ll dx = x[j] - x[i];
const ll dy = y[j] - y[i];
const R r(dy, dx);
if (r.is_munus_infinity()) {
const pair<pll, R> key = {{xx, yy}, -r};
mp[key]++;
} else {
const pair<pll, R> key = {{xx, yy}, r};
mp[key]++;
}
}
// dump(mp);
ll ans = 0;
for (const auto &[key, v] : mp) {
const auto &[xxyy, r] = key;
R ir = -r.inv();
if (ir.is_munus_infinity()) ir *= -1;
const pair<pll, R> needle_key = {xxyy, ir};
if (mp.contains(needle_key)) ans += v * mp.at(needle_key);
}
pprint(ans / 2);
}
// entry point
int main() {
solve();
return 0;
}