結果

問題 No.2953 Maximum Right Triangle
ユーザー eve__fuyukieve__fuyuki
提出日時 2024-11-08 23:11:04
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 1,078 bytes
コンパイル時間 2,191 ms
コンパイル使用メモリ 201,068 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-08 23:11:10
合計ジャッジ時間 2,604 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

void fast_io() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
}
void solve() {
	long long d, x, y;
	cin >> d >> x >> y;
	long long dx = x, dy = y;
	long long g = gcd(x, y);
	dx /= g;
	dy /= g;
	long long ok_h = 0, ng_h = d + 1;
	auto is_ok = [&](long long h) -> bool {
		long long xx = x + h * dy;
		long long yy = y - h * dx;
		return xx >= 0 && yy >= 0 && xx <= d && yy <= d;
	};
	while (ok_h + 1 < ng_h) {
		long long mid = (ok_h + ng_h) / 2;
		if (is_ok(mid)) {
			ok_h = mid;
		} else {
			ng_h = mid;
		}
	}
	long long ng_l = -d - 1, ok_l = 0;
	while (ng_l + 1 < ok_l) {
		long long mid = (ng_l + ok_l) / 2;
		if (is_ok(mid)) {
			ok_l = mid;
		} else {
			ng_l = mid;
		}
	}
	long long ans = 0;
	{
		long long xx = x + ok_h * dy;
		long long yy = y - ok_h * dx;
		ans = max(ans, abs(xx * y - yy * x));
	}
	{
		long long xx = x + ok_l * dy;
		long long yy = y - ok_l * dx;
		ans = max(ans, abs(xx * y - yy * x));
	}
	cout << ans << "\n";
}
int main() {
	fast_io();
	int t;
	cin >> t;
	for (; t--;) {
		solve();
	}
}
0