結果

問題 No.461 三角形はいくつ？
ユーザー vjudge1
提出日時 2025-07-27 15:10:27
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,423 bytes
コンパイル時間 1,999 ms
コンパイル使用メモリ 209,344 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-07-27 15:11:12
合計ジャッジ時間 40,355 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 29 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define int ll
#define fi first
#define endl '\n'
#define il inline
#define se second
#define pb push_back
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif
const int N = 4e3 + 10;
int n, ans, cnt, C[N];
vector<pii> a[2];
map<pii, int> c;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    a[0].pb({1, 0}), a[1].pb({1, 0}), C[c[{1, 0}] = cnt = 1] = 1e18;
    for (int i = 1, opt, x, y; i <= n; i++)
    {
        cin >> opt >> x >> y;
        if (opt < 2) a[opt].pb({x / __gcd(x, y), y / __gcd(x, y)});
        else c[{x / __gcd(x, y), y / __gcd(x, y)}]++, C[++cnt] = x * 1e9 / y;
    }
    sort(C + 1, C + cnt + 1);
    for (auto x : a[0])
        for (auto y : a[1])
        {
            int a = x.fi * y.se + x.se * y.fi + 2 * x.se * y.se, b = x.fi * y.fi - x.se * y.se;
            int p = a / __gcd(a, b), q = b / __gcd(a, b);
            if (p < 0 || q < 0) continue;
            ans += cnt - (prev(lower_bound(C + 1, C + cnt + 1, max(x.se * 1e9 / x.fi, y.se * 1e9 / y.fi))) - C);
            if (c.count({p, q})) ans -= c[{p, q}];
            // cout << x.fi << ' ' << x.se << ' ' << y.fi << ' ' << y.se << ' ' << p << ' ' << q << endl;
        }
    cout << ans << endl;
    return 0;
}
0