結果
問題 | No.2953 Maximum Right Triangle |
ユーザー |
![]() |
提出日時 | 2024-11-09 13:00:24 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,094 bytes |
コンパイル時間 | 3,210 ms |
コンパイル使用メモリ | 246,696 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-09 13:00:29 |
合計ジャッジ時間 | 4,015 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 6 |
ソースコード
#include <bits/stdc++.h>void solve() {long long D, x, y; std::cin >> D >> x >> y;long long L = std::gcd(x, y);std::pair<long long, long long> v = {-y / L, x / L};long long ans = 0;long long ac = 0, wa = 1 << 30;while (wa - ac > 1) {long long wj = (ac + wa) / 2;long long a = x + v.first * wj, b = y + v.second * wj;if (0 <= a && a <= D && 0 <= b && b <= D) {ac = wj;} else {wa = wj;}}long long a = x + v.first * ac, b = y + v.second * ac;ans = std::abs(x * b - y * a);ac = 0, wa = 1 << 30;while (wa - ac > 1) {long long wj = (ac + wa) / 2;long long c = x - v.first * wj, d = y - v.second * wj;if (0 <= c && c <= D && 0 <= d && d <= D) {ac = wj;} else {wa = wj;}}long long c = x - v.first * ac, d = y - v.second * ac;ans = std::max(ans, std::abs(x * d - y * c));std::cout << ans << '\n';}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int testcases = 1;std::cin >> testcases;for (;testcases--;) {solve();}return 0;}