QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#660819#2140. Lots of Parabolasiris2617#AC ✓49ms5876kbC++201.5kb2024-10-20 13:31:352024-10-20 13:31:35

Judging History

This is the latest submission verdict.

  • [2024-10-20 13:31:35]
  • Judged
  • Verdict: AC
  • Time: 49ms
  • Memory: 5876kb
  • [2024-10-20 13:31:35]
  • Submitted

answer

#include<bits/stdc++.h>
#define int long long
#define matsuri pair<int,int>
//const int iris = 1e9+7;
const int iris = 998244353;
using namespace std;

void solve()
{
	int n;
	cin>>n;
	vector<tuple<int,int,int> > arr, brr;
	
	for(int i=0;i<n;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		if(a>0)
			arr.emplace_back(a,b,c);
		else
			brr.emplace_back(a,b,c);
	}
	cout<<fixed<<setprecision(12);
	if(brr.empty())
	{
		long double x=0, y=-1e18;
		for(auto [a,b,c]:arr)
			y=max(y, (long double)c);
		cout<<x<<' '<<y+1<<'\n';
		return;
	}
	if(arr.empty())
	{
		long double x=0, y=1e18;
		for(auto [a,b,c]:brr)
			y=min(y, (long double)c);
		cout<<x<<' '<<y-1<<'\n';
		return;
	}
	
	auto cal=[&](long double x)->pair<bool, long double>
	{
		long double l=-1e50,r=1e50;
		for(auto [a,b,c]:arr)
			l=max(l, a*x*x+b*x+c);
		for(auto [a,b,c]:brr)
			r=min(r, a*x*x+b*x+c);
		//cout<<' '<<l<<' '<<r<<'\n';
		if(l<r)
			return {true, (l+r)/2};
		else
			return {false, (l-r)};
	};
	
	long double l=-3e9, r=3e9;
	int cnt=0;
	while(1)
	{
		long double m1=l+(r-l)/3;
		long double m2=l+(r-l)/3*2;
		auto [b1, y1]=cal(m1);
		auto [b2, y2]=cal(m2);
		//cout<<" - "<<l<<' '<<r<<' '<<m1<<' '<<m2<<' '<<y1<<' '<<y2<<'\n';
		if(b1)
		{
			cout<<m1<<' '<<y1<<'\n';
			return;
		}
		if(b2)
		{
			cout<<m2<<' '<<y2<<'\n';
			return;
		}
		
		if(y1>y2)
			l=m1;
		else
			r=m2;
	}
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T=1;
	//cin>>T;
	while(T--)
		solve();

	return 0;
}

詳細信息

Test #1:

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

input:

4
1 2 3
1 -3 -5
-1 3 4
-2 4 6

output:

0.011236668122 3.528091670306

result:

ok Point (0.0112367, 3.5280917)

Test #2:

score: 0
Accepted
time: 0ms
memory: 3880kb

input:

1
-22 -12 39

output:

0.000000000000 38.000000000000

result:

ok Point (0.0000000, 38.0000000)

Test #3:

score: 0
Accepted
time: 0ms
memory: 3992kb

input:

1
26 88 45

output:

0.000000000000 46.000000000000

result:

ok Point (0.0000000, 46.0000000)

Test #4:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

2
4 -1 1
-4 4 3

output:

0.011236668122 2.016855002184

result:

ok Point (0.0112367, 2.0168550)

Test #5:

score: 0
Accepted
time: 0ms
memory: 3988kb

input:

2
-4 -3 -1
-2 0 2

output:

0.000000000000 -2.000000000000

result:

ok Point (0.0000000, -2.0000000)

Test #6:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

2
2 9 7
5 9 0

output:

0.000000000000 8.000000000000

result:

ok Point (0.0000000, 8.0000000)

Test #7:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

20
-6 -41 -65
-1 -11 -22
-8 -61 -113
7 56 109
-4 -40 -87
-9 -82 -175
8 55 87
8 67 140
-6 -43 -64
-2 -18 -28
9 76 159
2 18 41
3 34 88
-10 -86 -174
3 30 66
8 71 153
1 4 -1
-6 -48 -88
-3 -28 -52
7 51 91

output:

-3.752353719326 2.956379123550

result:

ok Point (-3.7523537, 2.9563791)

Test #8:

score: 0
Accepted
time: 0ms
memory: 4000kb

input:

20
11 -155 -190
-46 450 -439
33 -348 -52
-8 348 434
-9 415 244
27 -294 -73
-14 303 -332
12 -197 294
-26 405 111
-41 475 161
4 -297 123
35 -483 238
21 -271 339
-41 386 -316
20 -257 -424
1 -178 -219
-37 369 -183
12 -64 -487
-40 465 385
-21 245 20

output:

1.620407102812 64.255857270175

result:

ok Point (1.6204071, 64.2558573)

Test #9:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

20
-28 662 -2672
9 -338 1137
-6 449 -1877
-5 397 -1133
-31 725 -2794
11 -338 1167
-29 727 -2831
-12 553 -1595
15 -428 1059
-2 146 -773
19 -524 2151
13 -541 2115
-3 520 -2269
5 -331 1484
20 -531 1662
2 -402 1117
-5 343 -1650
-4 216 -407
17 -440 1222
2 -235 957

output:

19.484649441215 -641.202114240116

result:

ok Point (19.4846494, -641.2021142)

Test #10:

score: 0
Accepted
time: 0ms
memory: 4000kb

input:

40
-27 127 -124
-9 8 53
11 -77 90
-12 45 -21
-25 106 -97
-8 50 -45
-19 76 -46
19 -111 126
-3 14 -2
-3 4 31
-21 116 -124
2 -36 64
9 -22 -7
21 -118 121
-35 117 -64
10 -58 50
32 -106 64
15 -45 20
3 -49 77
6 -5 -46
27 -98 78
-21 120 -124
-10 17 39
-10 33 -2
10 -61 75
-35 171 -198
-37 116 -50
-10 23 30
3...

output:

2.184025173845 6.387232197729

result:

ok Point (2.1840252, 6.3872322)

Test #11:

score: 0
Accepted
time: 0ms
memory: 3992kb

input:

40
-27 -87 -64
-9 -48 -43
-8 -47 -24
-34 -97 -43
-19 -42 -7
-22 -73 -47
-2 -20 23
-5 -3 42
-25 -53 6
-19 -66 -6
-37 -96 -45
-4 -18 -12
-13 -50 -9
-14 -42 -10
-27 -87 -64
-3 9 41
-12 -31 9
-19 -59 -30
-8 -32 5
-9 -52 -5
-2 -33 -44
-1 -21 4
-2 16 49
-30 -65 5
-25 -52 11
-35 -106 -65
-5 -33 -29
-27 -49...

output:

0.000000000000 -66.000000000000

result:

ok Point (0.0000000, -66.0000000)

Test #12:

score: 0
Accepted
time: 0ms
memory: 3880kb

input:

40
30 83 45
2 -7 -26
5 16 -27
29 98 66
27 75 22
8 14 -18
2 -14 -32
15 33 2
1 -7 -56
18 54 32
11 55 25
17 49 3
27 81 32
9 66 61
1 -33 -63
25 82 25
27 95 63
19 50 -5
18 86 60
29 116 77
25 75 20
17 56 17
33 126 80
37 141 105
35 107 56
25 81 34
23 78 24
5 -6 -34
1 -9 -54
13 55 19
12 20 -2
22 54 -5
4 -11...

output:

0.000000000000 106.000000000000

result:

ok Point (0.0000000, 106.0000000)

Test #13:

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

input:

1000
-6 -502 -10522
-3 -247 -5101
-9 -746 -15479
8 654 13333
1 86 1820
-6 -493 -10143
9 744 15345
2 174 3747
6 503 10502
-6 -493 -10151
-7 -582 -12113
-10 -826 -17079
6 499 10336
9 742 15263
-1 -91 -2076
-7 -581 -12070
7 580 11982
-3 -252 -5305
-3 -255 -5435
1 88 1903
-11 -897 -18302
10 826 17020
-3...

output:

-41.682710991012 -26.610511531456

result:

ok Point (-41.6827110, -26.6105115)

Test #14:

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

input:

1000
-166 -2543 -9416
176 2467 7478
-410 -5077 -14109
153 2052 6285
-20 -875 -3813
-131 -1726 -5046
-192 -2643 -7536
89 1375 4584
23 938 3475
160 2598 8283
-57 -915 -3052
78 1661 5492
252 3409 10190
110 2021 6478
201 2943 9107
-124 -1836 -5559
-120 -2077 -8334
-179 -2716 -9419
-142 -2315 -8410
-170 ...

output:

-7.892611998865 68.582950955876

result:

ok Point (-7.8926120, 68.5829510)

Test #15:

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

input:

10000
9 -798 17696
8 -699 15275
9 -784 17082
-9 797 -17624
-5 440 -9659
1 -86 1862
-3 265 -5828
-2 176 -3848
3 -265 5865
-11 964 -21105
-10 870 -18903
-1 83 -1694
-1 89 -1955
8 -702 15407
8 -698 15230
-2 173 -3717
-2 167 -3458
1 -89 1983
-11 959 -20882
11 -968 21305
-1 96 -2269
-9 801 -17797
-6 517 ...

output:

43.828674947284 14.329667284597

result:

ok Point (43.8286749, 14.3296673)

Test #16:

score: 0
Accepted
time: 6ms
memory: 3864kb

input:

10000
-421 14556 -124781
-124 3579 -24534
-531 18585 -161507
-616 21639 -189351
298 -10130 84921
-620 21770 -190491
-9 -399 10186
473 -16314 140202
443 -15338 132570
-828 29509 -262207
-653 23405 -208976
35 -923 4934
-366 12616 -107602
-835 29380 -257754
711 -24721 214343
152 -4787 36687
-454 16420 ...

output:

16.928735532147 25.264095314798

result:

ok Point (16.9287355, 25.2640953)

Test #17:

score: 0
Accepted
time: 49ms
memory: 5876kb

input:

100000
-2 63 -524
7 -230 1846
2 -76 676
-3 111 -1051
9 -309 2615
-6 193 -1572
5 -162 1266
4 -135 1100
-8 273 -2356
4 -145 1275
-1 35 -335
2 -64 471
-6 212 -1903
10 -346 2955
7 -247 2143
7 -243 2073
-2 64 -536
5 -164 1307
-4 147 -1376
2 -63 453
8 -282 2438
-8 276 -2406
8 -277 2359
-8 269 -2288
9 -311...

output:

17.036683337953 -33.198394190534

result:

ok Point (17.0366833, -33.1983942)

Test #18:

score: 0
Accepted
time: 48ms
memory: 5660kb

input:

100000
4 -168 -13660
-150 -11449 -217016
-41 -2841 -48412
-5 19 9797
-37 -2917 -56947
-34 -2174 -32412
4 -51 -7991
-14 -965 -16295
176 13449 254899
33 2118 31281
-25 -1424 -16827
-127 -9641 -181637
9 41 -13903
-5 83 11897
-146 -11529 -226526
150 11740 228177
-45 -3572 -70102
52 3751 66954
-24 -1172 ...

output:

-36.839641049865 -32.980473716786

result:

ok Point (-36.8396410, -32.9804737)

Test #19:

score: 0
Accepted
time: 0ms
memory: 3788kb

input:

100
-37 2220 -28638
-25 1500 -18582
13 -780 8158
35 -2100 26902
41 -2460 31846
33 -1980 25238
-7 420 -2958
19 -1140 13366
-47 2820 -36798
-50 3000 -39207
30 -1800 22727
-46 2760 -35991
22 -1320 15943
-2 120 1497
-43 2580 -33558
-35 2100 -26982
-31 1860 -23646
15 -900 9902
-13 780 -8238
-20 1200 -143...

output:

25.904611531579 -40.000000000000

result:

ok Point (25.9046115, -40.0000000)

Test #20:

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

input:

1000
425 -16150 -360507
367 -13946 -335509
-480 18240 390479
-101 3838 307099
32 -1216 -322779
196 -7448 -300967
-285 10830 311699
-59 2242 315541
-408 15504 352535
299 -11362 -314769
-186 7068 300809
289 -10982 -312499
-400 15200 348959
286 -10868 -311857
-69 2622 313211
44 -1672 -319359
187 -7106 ...

output:

25.904611531579 26.000000000000

result:

ok Point (25.9046115, 26.0000000)

Test #21:

score: 0
Accepted
time: 0ms
memory: 3848kb

input:

100
-46 0 2115
20 1200 98
21 1260 957
-40 0 1599
-48 0 2303
40 2400 16898
44 2640 20162
6 360 -12138
26 1560 5222
4 240 -13918
-8 0 63
-41 0 1680
-28 0 783
-7 0 48
7 420 -11251
2 120 -15706
-50 0 2499
39 2340 16077
-45 0 2024
38 2280 15254
-11 0 120
12 720 -6846
-4 0 15
43 2580 19349
-36 0 1295
-37 ...

output:

-15.038026570548 -8808.539855822222

result:

ok Point (-15.0380266, -8808.5398558)

Test #22:

score: 0
Accepted
time: 0ms
memory: 3932kb

input:

200
6 300 -13785
-77 -1041 6339
-19 7 -1320
70 1708 -10263
4 200 -15015
-24 240 -22
1 50 -16875
23 1150 -3653
34 1154 -8803
9 2019 -12750
-10 100 -148
-43 430 776
-145 -683 8289
48 1298 -9257
15 1451 -9707
26 1300 -1925
8 400 -12563
31 1936 -8437
68 1315 -9083
-15 -2032 9169
-8 80 -134
-18 180 -124
...

output:

-9.951446591497 -8675.669887244784

result:

ok Point (-9.9514466, -8675.6698872)

Test #23:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

1000
-97 1940 -316
27 1080 -15267
165 6600 13437
262 10480 10818
-197 3940 19084
-179 3580 14116
466 18640 -56094
279 11160 8421
142 5680 11298
-360 7200 93575
258 10320 11298
-123 2460 2804
-206 4120 21811
-99 1980 -124
448 17920 -46842
-301 6020 60476
390 15600 -21438
-386 7720 110371
-473 9460 17...

output:

-5.001686007540 -12687.190276870053

result:

ok Point (-5.0016860, -12687.1902769)

Test #24:

score: 0
Accepted
time: 44ms
memory: 5652kb

input:

100000
10754 172263 -698885
-8838 -170969 640201
10066 101427 -639428
411 98897 -487244
1885 20325 -164846
1470 109370 -454536
675 201125 -592526
1597 227993 -895510
3331 98310 -248590
-1083 -157235 261847
3290 196532 -837407
-6277 -98357 388691
-9485 -126213 680029
-903 -52026 80842
-1453 -64709 24...

output:

-11.980401429794 -12609.354633501792

result:

ok Point (-11.9804014, -12609.3546335)