結果
問題 |
No.2769 Number of Rhombi
|
ユーザー |
![]() |
提出日時 | 2024-06-15 22:28:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,158 ms / 5,000 ms |
コード長 | 1,502 bytes |
コンパイル時間 | 761 ms |
コンパイル使用メモリ | 65,192 KB |
最終ジャッジ日時 | 2025-02-21 22:59:56 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:52:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 52 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:53:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 53 | for (int i = 0; i < n; i++) scanf("%d%d", xs + i, ys + i); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*- * * 2769.cc: No.2769 Number of Rhombi - yukicoder */ #include<cstdio> #include<map> #include<algorithm> #include<tuple> using namespace std; /* constant */ const int MAX_N = 1000; const int MAX_M = MAX_N * (MAX_N - 1) / 2; /* typedef */ using ll = long long; using tp4 = tuple<int,int,int,int>; using mtp4i = map<tp4,int>; /* global variables */ int xs[MAX_N], ys[MAX_N]; tp4 es[MAX_M]; /* subroutines */ template <typename T> T gcd(T m, T n) { // m >= 0, n >= 0 if (m < n) swap(m, n); while (n > 0) { T r = m % n; m = n; n = r; } return m; } void normalize(int &x, int &y) { if (x == 0) y = 1; else if (y == 0) x = 1; else if (x < 0) x = -x, y = -y; } /* main */ int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d%d", xs + i, ys + i); mtp4i ecs; int m = 0; for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) { int cx = xs[i] + xs[j], cy = ys[i] + ys[j]; int dx = xs[j] - xs[i], dy = ys[j] - ys[i]; if (dx == 0) dy = 1; int g = gcd(abs(dx), abs(dy)); if (g > 1) dx /= g, dy /= g; normalize(dx, dy); tp4 e(cx, cy, dx, dy); ecs[e]++; es[m++] = e; } ll sum = 0; for (int i = 0; i < m; i++) { auto [cx, cy, dx, dy] = es[i]; int rx = -dy, ry = dx; normalize(rx, ry); auto mit = ecs.find(tp4(cx, cy, rx, ry)); if (mit != ecs.end()) sum += mit->second; } printf("%lld\n", sum / 2); return 0; }