結果
問題 | No.2953 Maximum Right Triangle |
ユーザー |
![]() |
提出日時 | 2024-11-10 01:09:14 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,462 bytes |
コンパイル時間 | 2,200 ms |
コンパイル使用メモリ | 201,324 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-10 01:09:27 |
合計ジャッジ時間 | 2,245 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 6 |
ソースコード
#include <bits/stdc++.h>//#include <atcoder/modint>using namespace std;//using namespace atcoder;using ll = long long;//using mint = modint998244353;//calculate ceil(a/b)template<typename T>T ceil(T a, T b){assert(b != 0);if (a == 0) return 0;if (a > 0 && b > 0) return (a+b-1) / b;else if (a < 0 && b < 0) return (a+b+1) / b;else return a / b;}//calculate floor(a/b)template<typename T>T floor(T a, T b){assert(b != 0);if (a == 0) return 0;if (a > 0 && b < 0) return (a-b-1) / b;else if (a < 0 && b > 0) return (a-b+1) / b;else return a / b;}int main(){cin.tie(nullptr);ios_base::sync_with_stdio(false);int T;cin >> T;while(T--){ll D, x, y, l1=-2e9, r1=2e9, l2=-2e9, r2=2e9, l, r, ans, g, x2, y2, x3, y3;cin >> D >> x >> y;g = gcd(x, y);x2 = x/g;y2 = y/g;//ありうるのは(x-ny2, y+nx2) (nは整数)//0<=x-ny2<=D, 0<=y+nx2<=Dif (y2 != 0) l1 = ceil(x-D, y2);if (y2 != 0) r1 = floor(x, y2);if (x2 != 0) l2 = ceil(-y, x2);if (x2 != 0) r2 = floor(D-y, x2);l = max(l1, l2);r = min(r1, r2);if (l>r){cout << 0 << endl;}else{g = max(abs(l), abs(r));x3 = x-g*y2;y3 = y+g*x2;ans = abs(x3*y-y3*x);cout << ans << endl;}}return 0;}