結果
問題 | No.2769 Number of Rhombi |
ユーザー |
|
提出日時 | 2024-05-31 23:00:12 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 915 ms / 5,000 ms |
コード長 | 1,058 bytes |
コンパイル時間 | 2,641 ms |
コンパイル使用メモリ | 218,872 KB |
実行使用メモリ | 127,104 KB |
最終ジャッジ日時 | 2024-12-21 01:13:01 |
合計ジャッジ時間 | 23,502 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include <bits/stdc++.h>using namespace std;int main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);int N; cin >> N;vector<pair<long long,long long>> XY(N);for(auto &[x,y] : XY) cin >> x >> y,x *= 2, y *= 2;map<pair<long long,long long>,map<pair<long long,long long>,long long>> M;for(int i=0; i<N; i++) for(int k=i+1; k<N; k++){auto[x1,y1] = XY.at(i);auto[x2,y2] = XY.at(k);if(x1 > x2) swap(x1,x2),swap(y1,y2);long long mx = (x1+x2)/2,my = (y1+y2)/2;if(x1 == x2) M[{mx,my}][{0,1}]++;else if(y1 == y2) M[{mx,my}][{1,0}]++;else{long long dx = abs(x2-x1),dy = abs(y2-y1),g = gcd(dx,dy);M[{mx,my}][{(x2-x1)/g,(y2-y1)/g}]++;}}long long answer = 0;for(auto &[ig,V] : M){for(auto &[k,v] : V){auto &[x,y] = k;if(x < 0 || y == 0) continue;if(x == 0) answer += v*V[{1,0}];else answer += v*V[{y,-x}];}}cout << answer << endl;}