結果
問題 | No.2953 Maximum Right Triangle |
ユーザー | daiota |
提出日時 | 2024-11-09 02:31:23 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,321 bytes |
コンパイル時間 | 1,735 ms |
コンパイル使用メモリ | 168,780 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-09 02:31:39 |
合計ジャッジ時間 | 2,236 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | WA | - |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | WA | - |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> P; #define REP(i,n) for(int i=0;i<int(n);i++) ll extgcd(ll a,ll b,ll & x,ll & y){ ll g; if(b!=0){ g=extgcd(b,a%b,y,x); y-=(a/b)*x; }else{ g=a; x=1; y=0; } return g; } int main(void){ cin.tie(nullptr); ios_base::sync_with_stdio(false); ll i,j; int T; cin >> T; while(T--){ ll D,a,b; cin >> D >> a >> b; if(a==0){ cout << b*D << endl; continue; } if(b==0){ cout << a*D << endl; continue; } ll x,y; ll c=a*a+b*b; ll g=extgcd(a,b,x,y); if(c%g!=0){ cout << 0 << endl; continue; } double p=-1.0*c*x/b,q=1.0*(D*g-c*x)/b; double pp=1.0*(c*y-D*g)/a,qq=1.0*c*y/a; if(max(p,pp)>min(q,qq)){ cout << 0 << endl; continue; } ll u=(ll)(max(p,pp)),v=(ll)(min(q,qq)); ll X,Y,s=0,S=0; for(i=u-1;i<=u+1;i++){ X=c*x/g+b*i/g; Y=c*y/g-a*i/g; if(!(X>=0 && X<=D)) continue; if(!(Y>=0 && Y<=D)) continue; s=max(s,2*max(a,X)*max(b,Y)-(a*b+X*Y+llabs(X-a)*llabs(Y-b))); } for(i=v-1;i<=v+1;i++){ X=c*x/g+b*i/g; Y=c*y/g-a*i/g; if(!(X>=0 && X<=D)) continue; if(!(Y>=0 && Y<=D)) continue; S=max(S,2*max(a,X)*max(b,Y)-(a*b+X*Y+llabs(X-a)*llabs(Y-b))); } cout << max(s,S) << endl; } return 0; }