結果
問題 | No.2769 Number of Rhombi |
ユーザー |
![]() |
提出日時 | 2024-01-07 01:13:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 954 ms / 5,000 ms |
コード長 | 1,391 bytes |
コンパイル時間 | 2,347 ms |
コンパイル使用メモリ | 207,896 KB |
最終ジャッジ日時 | 2025-02-18 16:25:05 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; //fraction (p/q) struct fraction{ ll p, q; fraction(ll P=0, ll Q=1) : p(P), q(Q) { assert (P != 0 || Q != 0); ll g = gcd(P, Q); p /= g; q /= g; if (q < 0){ p *= -1; q *= -1; } if (p == 0) q = 1; if (q == 0) p = 1; } bool operator < (const fraction & other) const{ if (p < 0) return -p*other.q > -other.p*q; return p*other.q < other.p*q; } bool operator == (const fraction & other) const{ return p*other.q == other.p*q; } bool operator > (const fraction & other) const{ if (p < 0) return -p*other.q < -other.p*q; return p*other.q > other.p*q; } }; int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); ll N, ans=0; cin >> N; vector<ll> x(N), y(N); for (int i=0; i<N; i++) cin >> x[i] >> y[i]; map<tuple<ll, ll, fraction>, ll> mp; for (int i=0; i<N; i++){ for (int j=i+1; j<N; j++){ fraction p(y[i]-y[j], x[i]-x[j]); mp[{x[i]+x[j], y[i]+y[j], p}]++; } } for (auto [a, b] : mp){ fraction p, q; ll xx, yy; tie(xx, yy, p) = a; q = fraction(-p.q, p.p); ans += mp[{xx, yy, q}] * b; } cout << ans/2 << endl; return 0; }