結果
問題 | 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;}