QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#513108#9168. Square Locatorucup-team3661#RE 0ms3596kbC++202.3kb2024-08-10 16:56:322024-08-10 16:56:32

Judging History

你现在查看的是最新测评结果

  • [2024-08-10 16:56:32]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3596kb
  • [2024-08-10 16:56:32]
  • 提交

answer

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

using ll = long long;

int main(){
	vector<ll> LEN(4);
	for(int i = 0; i < 4; ++i) cin >> LEN[i];

	vector<int> p(4);
	iota(p.begin(), p.end(), 0);
	
	ll left = 1, right = 1000000010;
	while(right-left > 1){
		ll mid = (right+left)>>1;
		if(mid*mid > LEN[0]){
			right = mid;
		}else{
			left = mid;
		}
	}

	ll ay = left;

	do{
		if(p[0] != 0) break;
		ll BD = LEN[p[3]]-LEN[p[1]];
		if(BD%ay != 0) continue;
		if((BD/ay)%2 != 0) continue;
		__int128_t alpha = BD/ay/2;

		__int128_t CA = LEN[p[1]]-alpha*alpha-LEN[p[0]];
		if(CA%2 != 0) continue;
		__int128_t beta = -CA/2;

		__int128_t H = alpha+ay;
		H *= alpha+ay;
		H += -beta*4;

		__int128_t leftL = 1, rightL = 2000000000000000000LL;
		while(rightL-leftL > 1){
			__int128_t mid = (leftL+rightL)>>1;
			if(mid*mid > H){
				rightL = mid;
			}else{
				leftL = mid;
			}
		}
		if(leftL*leftL != H) continue;

		if((leftL+alpha)%2) continue;

		{
			ll ly = (leftL-alpha-ay)/2;
			ll lx = alpha+ly;

			vector<ll> ansx(4), ansy(4);
			ansx[p[0]] = 0;
			ansx[p[1]] = ansx[p[0]] + lx;
			ansx[p[2]] = ansx[p[0]] + lx - ly;
			ansx[p[3]] = ansx[p[0]] - ly;
			ansy[p[0]] = ay;
			ansy[p[1]] = ansy[p[0]] + ly;
			ansy[p[2]] = ansy[p[0]] + lx + ly;
			ansy[p[3]] = ansy[p[0]] + lx;
			
			bool flag = true;
			for(int i = 0; i < 4; ++i){
				flag &= (ansx[i]*ansx[i]+ansy[i]*ansy[i]) == LEN[i];
			}
			if(true){
				cout << ansy[0] << ' ' << ansx[1] << ' ' << ansy[1] << ' ' << ansx[2] << ' ' << ansy[2] << ' ' << ansx[3] << ' ' << ansy[3] << endl;
				return 0;
			}
		}

		{
			ll ly = (-leftL-alpha-ay)/2;
			ll lx = alpha+ly;

			vector<ll> ansx(4), ansy(4);
			ansx[p[0]] = 0;
			ansx[p[1]] = ansx[p[0]] + lx;
			ansx[p[2]] = ansx[p[0]] + lx - ly;
			ansx[p[3]] = ansx[p[0]] - ly;
			ansy[p[0]] = ay;
			ansy[p[1]] = ansy[p[0]] + ly;
			ansy[p[2]] = ansy[p[0]] + lx + ly;
			ansy[p[3]] = ansy[p[0]] + lx;
			
			bool flag = true;
			for(int i = 0; i < 4; ++i){
				flag &= (ansx[i]*ansx[i]+ansy[i]*ansy[i]) == LEN[i];
			}
			if(true){
				cout << ansy[0] << ' ' << ansx[1] << ' ' << ansy[1] << ' ' << ansx[2] << ' ' << ansy[2] << ' ' << ansx[3] << ' ' << ansy[3] << endl;
				return 0;
			}
		}

	}while(next_permutation(p.begin(), p.end()));
	assert(false);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3596kb

input:

36 5 10 41

output:

6 -1 2 3 1 4 5

result:

ok Answer is correct

Test #2:

score: -100
Runtime Error

input:

1 1 1 1

output:


result: