結果

問題 No.2953 Maximum Right Triangle
コンテスト
ユーザー daiota
提出日時 2024-11-09 02:31:23
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;

}
0