QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#326719#6763. Triangle PendantmshcherbaAC ✓5ms4424kbC++203.3kb2024-02-13 20:31:532024-02-13 20:31:53

Judging History

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

  • [2024-02-13 20:31:53]
  • 评测
  • 测评结果:AC
  • 用时:5ms
  • 内存:4424kb
  • [2024-02-13 20:31:53]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const db EPS = 1e-9;

void print(db a, db b, db c, int i)
{
	if (i == 0)
		cout << a << " " << b << " " << c << "\n";
	else if (i == 1)
		cout << c << " " << a << " " << b << "\n";
	else
		cout << b << " " << c << " " << a << "\n";
}

db getMedian(db a, db b, db c)
{
	return sqrt(2 * (b * b + c * c) - a * a) / 2;
}

db getCos(db a, db b, db c)
{
	db res = (b * b + c * c - a * a) / (2 * b * c);
	assert(-1 - EPS < res && res < 1 + EPS);
	return res;
}

db getThirdSide(db b, db c, db co)
{
	return sqrt(b * b + c * c - 2 * b * c * co);
}

bool solve1(db x, db y, db z, db a, db b, db c, int i)
{
	db m = getMedian(a, b, c);
	db coB = getCos(a / 2, b, m), coC = getCos(a / 2, c, m);
	db hb = -x - c * coC, hc = -x - b * coB;
	if (getThirdSide(x, c, -coC) > y + EPS || getThirdSide(x, b, -coB) > z + EPS)
		return false;
	print(-x, hb, hc, i);
	return true;
}

bool solve2(db x, db y, db z, db a, db b, db c, int i)
{
	if (2 * max({x, y, c}) > x + y + c + EPS)
		return false;
	db mA = getMedian(a, b, c), mB = getMedian(b, c, a), mC = getMedian(c, a, b);
	db AM = 2 * mA / 3, BM = 2 * mB / 3, CM = 2 * mC / 3;
	db MAB = acos(getCos(BM, AM, c)), MBA = acos(getCos(AM, BM, c));
	db DAB = acos(getCos(y, x, c)), DBA = acos(getCos(x, y, c));
	db DM1 = getThirdSide(x, AM, cos(MAB + DAB));
	db DM2 = getThirdSide(y, BM, cos(MBA + DBA));
	assert(abs(DM1 - DM2) < EPS);
	db CAB = acos(getCos(a, b, c)), CBA = acos(getCos(b, a, c));
	db DC1 = getThirdSide(x, b, cos(CAB + DAB));
	db DC2 = getThirdSide(y, a, cos(CBA + DBA));
	assert(abs(DC1 - DC2) < EPS);
	db ADB = acos(getCos(c, x, y)), ADM = acos(getCos(AM, x, DM1)), BDM = acos(getCos(BM, y, DM2));
	if (DC1 > z + EPS || abs(ADB - ADM - BDM) > EPS)
		return false;
	db cosCDM = getCos(CM, DM1, DC1);
	print(-x * getCos(AM, x, DM1), -y * getCos(BM, y, DM2), -DC1 * cosCDM, i);
	return true;
}

pair<db, db> getH(db x, db y, db z, db a, db b, db c)
{
	db ma = getMedian(a, y, z), mA = getMedian(a, b, c);
	db cosA = getCos(ma, x, mA);
	db l = getThirdSide(2 * mA / 3, x, cosA);
	cosA = getCos(2 * mA / 3, x, l);
	return {-x * cosA, l};
}

void solve()
{
	db x, y, z, a, b, c;
	cin >> x >> y >> z >> a >> b >> c;
	int ok1 = 0, ok2 = 0;
	if (solve1(x, y, z, a, b, c, 0))
		ok1++;
	if (solve1(y, z, x, b, c, a, 1))
		ok1++;
	if (solve1(z, x, y, c, a, b, 2))
		ok1++;
	assert(ok1 <= 1);
	if (ok1)
		return;
	if (solve2(x, y, z, a, b, c, 0))
		ok2++;
	if (solve2(y, z, x, b, c, a, 1))
		ok2++;
	if (solve2(z, x, y, c, a, b, 2))
		ok2++;
	assert(ok2 <= 1);
	if (ok2)
		return;
	auto [ans1, l1] = getH(x, y, z, a, b, c);
	auto [ans2, l2] = getH(y, z, x, b, c, a);
	auto [ans3, l3] = getH(z, x, y, c, a, b);
	assert(abs(l2 - l1) < EPS && abs(l3 - l1) < EPS);
	cout << ans1 << " " << ans2 << " " << ans3 << "\n";
}

int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);
	cout << fixed << setprecision(15);
	int t;
	cin >> t;
	while (t--)
		solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4352kb

input:

2
1 1 1 1 1 1
2 3 3 1 1 1

output:

-0.816496580927726 -0.816496580927726 -0.816496580927726
-2.000000000000000 -2.866025403784439 -2.866025403784439

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 3ms
memory: 4424kb

input:

1000
21 2 14 12 13 4
29 19 13 15 10 17
29 24 15 29 24 23
29 17 30 18 9 25
27 24 30 16 4 15
28 13 17 12 21 16
16 22 10 22 15 8
15 23 24 23 27 13
26 3 27 15 16 17
5 8 20 17 6 12
24 14 13 15 19 13
27 22 18 18 23 30
22 18 14 11 29 28
7 13 22 22 17 11
19 9 16 22 20 17
21 14 20 6 29 25
20 10 19 9 27 27
17...

output:

-2.935856727586833 -2.000000000000000 -13.352348999857675
-22.146476218003023 -16.076204705476876 -12.241826659011300
-28.027431433359670 -18.318582636182796 -8.243362186282258
-27.266119651334360 -13.159319584325656 -26.882525397692703
-26.534933366925674 -22.066632132649339 -29.616079568529663
-26...

result:

ok 3000 numbers

Test #3:

score: 0
Accepted
time: 3ms
memory: 4252kb

input:

1000
33 73 79 36 44 48
96 66 45 9 13 14
81 64 9 50 30 26
59 64 65 39 44 13
47 63 7 20 11 27
36 20 52 13 22 20
20 30 29 12 2 12
46 36 41 34 28 39
97 54 70 16 14 5
79 8 97 41 24 18
95 83 59 47 15 50
85 78 67 22 13 17
96 32 70 32 15 18
27 34 76 38 13 29
47 86 95 42 17 34
41 50 50 25 33 22
82 42 81 18 4...

output:

-32.015847290392884 -69.684039776767548 -75.638061984052811
-56.241370959657523 -51.194224814505169 -45.000000000000000
-37.905135499813412 -58.350854686242002 -9.000000000000000
-56.487522082654579 -62.826241045256339 -58.955695838003926
-7.960896812205176 -23.730909200748957 -7.000000000000000
-33...

result:

ok 3000 numbers

Test #4:

score: 0
Accepted
time: 5ms
memory: 4356kb

input:

1000
171 722 964 22 53 44
379 126 423 98 56 54
233 473 879 86 44 48
159 864 365 39 44 63
847 363 207 70 11 77
736 920 652 13 72 70
318 278 347 44 87 66
691 693 1000 64 50 19
879 8 297 91 74 68
536 888 163 33 44 27
495 83 959 97 65 100
968 643 337 32 61 46
204 797 870 52 62 59
885 978 167 72 63 17
22...

output:

-171.000000000000000 -213.850392599166810 -223.049554713779571
-177.405405405405418 -126.000000000000000 -222.594594594594582
-233.000000000000000 -255.050679634077568 -243.873475632231077
-159.000000000000000 -219.738578713327456 -199.696129350530072
-201.807639006052625 -276.325035973243189 -207.0...

result:

ok 3000 numbers

Test #5:

score: 0
Accepted
time: 1ms
memory: 4420kb

input:

1000
501 94 77 81 461 510
196 366 645 209 313 464
159 864 365 439 44 463
359 57 440 288 429 255
318 278 347 444 487 466
520 930 929 312 302 162
691 693 1000 564 250 519
33 292 661 856 572 306
410 665 850 503 313 592
947 186 395 292 817 634
466 581 266 563 125 647
672 653 583 469 216 496
554 457 945 ...

output:

-484.158538588081228 -22.705846490065905 -57.153345139618203
-52.426107263072389 -307.221896671166121 -309.334793607177630
-159.000000000000000 -620.756001522758652 -187.028645031214154
-197.471099288720751 -57.000000000000000 -251.038990245212432
-149.368244210288680 -117.560921904322697 -228.03547...

result:

ok 3000 numbers

Test #6:

score: 0
Accepted
time: 3ms
memory: 4296kb

input:

1000
79 26 423 98 56 54
33 473 79 86 44 48
59 64 365 39 44 63
95 83 959 97 65 100
4 97 870 52 62 59
405 53 8 11 66 75
96 3 407 45 46 67
57 847 5 38 42 72
77 173 16 68 47 53
54 57 945 80 52 83
795 18 100 67 56 72
67 42 748 48 3 50
29 35 566 52 38 18
23 56 116 35 37 15
800 12 62 54 99 74
7 696 95 38 3...

output:

-77.245731657992351 -25.995970870232835 -122.739840058137986
-33.000000000000000 -55.050679634077568 -43.873475632231091
-49.837583792988099 -55.920611549363890 -80.004560518101457
-83.888685265630201 -63.594872346937251 -138.120730907369364
-4.000000000000000 -56.988277917715749 -60.309480522244939...

result:

ok 3000 numbers

Test #7:

score: 0
Accepted
time: 3ms
memory: 4360kb

input:

1000
171 722 64 22 53 44
379 26 423 98 56 54
233 473 79 86 44 48
381 864 9 100 80 76
159 64 365 39 44 63
847 63 207 70 11 77
189 410 33 78 87 17
736 920 52 13 72 70
318 278 47 44 87 66
91 693 1000 64 50 19
879 8 297 91 74 68
536 888 63 33 44 27
95 83 959 97 65 100
968 643 37 32 61 46
4 797 870 52 62...

output:

-115.143181363696954 -81.047727121232327 -64.000000000000000
-77.405405405405403 -26.000000000000000 -122.594594594594597
-121.609344453051918 -164.296871189503946 -79.000000000000000
-80.245304603629450 -102.144476100646685 -9.000000000000000
-124.420643288021580 -64.000000000000000 -98.67930413572...

result:

ok 3000 numbers