結果
問題 | No.2953 Maximum Right Triangle |
ユーザー |
|
提出日時 | 2024-11-08 21:43:28 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,111 bytes |
コンパイル時間 | 1,069 ms |
コンパイル使用メモリ | 85,296 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-08 21:43:31 |
合計ジャッジ時間 | 1,591 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 6 |
ソースコード
#include <iostream>#include <numeric>#include <utility>using namespace std;using ll = long long;int main () {int T; cin >> T;for (int z = 0; z < T; z++) {int D, x, y; cin >> D >> x >> y;int d = gcd(x, y);auto v = make_pair(-y / d, x / d);auto ch = [&] (int mul) {ll nx = 1LL * mul * v.first + x;ll ny = 1LL * mul * v.second + y;if (nx < 0 || D < nx) return false;if (ny < 0 || D < ny) return false;return true;};auto bs = [&] () {int ok = 0, ng = 1000000000 + 10;while (1 < abs(ok - ng)) {int m = (ok + ng) / 2;if (ch(m)) {ok = m;}else {ng = m;}}return ok;};int p = bs();v.first = -v.first;v.second = -v.second;int q = bs();int r = max(p, q);ll area = (1LL * x * x + 1LL * y * y) / d * r;cout << area << "\n";}}