QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#660819 | #2140. Lots of Parabolas | iris2617# | AC ✓ | 49ms | 5876kb | C++20 | 1.5kb | 2024-10-20 13:31:35 | 2024-10-20 13:31:35 |
Judging History
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)