QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#141823 | #2140. Lots of Parabolas | As3b_team_f_masr | AC ✓ | 118ms | 4404kb | C++14 | 1.5kb | 2023-08-18 02:22:44 | 2023-08-18 02:22:48 |
Judging History
answer
#include <bits/stdc++.h>
typedef long double ld;
typedef long long ll;
using namespace std;
int di[] = {1, 0, -1, 0, 0, 1, -1, 1};
int dj[] = {0, 1, 0, -1, -1, 0, 1, -1};
const ll oo = 1e18, MOD = 1e9 + 7;
const int N = 1e6 + 5, M = 30005;
#define EPS 1e-9
vector<pair<int,pair<int,int>>>pos,ne;
ld solve(ld mid)
{
ld mny=-1e14,mxy=1e14;
for(auto x:pos)
{
ld a=x.first,b=x.second.first,c=x.second.second;
mny=max(mny,a*mid*mid+b*mid+c);
}
for(auto x:ne)
{
ld a=x.first,b=x.second.first,c=x.second.second;
mxy=min(mxy,a*mid*mid+b*mid+c);
}
return mxy-mny;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
int a,b,c;
cin>>a>>b>>c;
if(a>0)pos.push_back({a,{b,c}});
else ne.push_back({a,{b,c}});
}
ld lo=-1e10,hi=1e10;
while(hi-lo>EPS)
{
ld mid1=lo+(hi-lo)/3.0,mid2=hi-(hi-lo)/3.0;
ld tmp1=solve(mid1),tmp2=solve(mid2);
if(tmp1>tmp2)
{
hi=mid2;
}
else lo=mid1;
}
ld mid=lo,mny=-1e14,mxy=1e14;
for(auto x:pos)
{
ld a=x.first,b=x.second.first,c=x.second.second;
mny=max(mny,a*mid*mid+b*mid+c);
}
for(auto x:ne)
{
ld a=x.first,b=x.second.first,c=x.second.second;
mxy=min(mxy,a*mid*mid+b*mid+c);
}
cout<<fixed<<setprecision(10)<<lo<<" "<<(mny+mxy)/2.0;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3820kb
input:
4 1 2 3 1 -3 -5 -1 3 4 -2 4 6
output:
0.2499999997 4.1249999992
result:
ok Point (0.2500000, 4.1250000)
Test #2:
score: 0
Accepted
time: 1ms
memory: 3708kb
input:
1 -22 -12 39
output:
-0.2721519236 -49999999999979.6818199158
result:
ok Point (-0.2721519, -49999999999979.6796875)
Test #3:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
1 26 88 45
output:
-1.6920266189 49999999999985.2692298889
result:
ok Point (-1.6920266, 49999999999985.2656250)
Test #4:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
2 4 -1 1 -4 4 3
output:
0.3124999998 2.4687499997
result:
ok Point (0.3125000, 2.4687500)
Test #5:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
2 -4 -3 -1 -2 0 2
output:
-0.3740234383 -50000000000000.2187500000
result:
ok Point (-0.3740234, -50000000000000.2187500)
Test #6:
score: 0
Accepted
time: 1ms
memory: 3816kb
input:
2 2 9 7 5 9 0
output:
-1.5275219294 49999999999998.9594726562
result:
ok Point (-1.5275219, 49999999999998.9609375)
Test #7:
score: 0
Accepted
time: 1ms
memory: 3748kb
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.9500000003 2.1174999993
result:
ok Point (-3.9500000, 2.1175000)
Test #8:
score: 0
Accepted
time: 1ms
memory: 3720kb
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:
5.4999999993 70.1250000484
result:
ok Point (5.5000000, 70.1250000)
Test #9:
score: 0
Accepted
time: 1ms
memory: 3820kb
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:
14.9657938571 -231.8287743025
result:
ok Point (14.9657939, -231.8287743)
Test #10:
score: 0
Accepted
time: 1ms
memory: 3576kb
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.1587793286 7.1572304675
result:
ok Point (2.1587793, 7.1572305)
Test #11:
score: 0
Accepted
time: 1ms
memory: 3728kb
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:
-1.7056228403 -49999999999997.9417839050
result:
ok Point (-1.7056228, -49999999999997.9453125)
Test #12:
score: 0
Accepted
time: 1ms
memory: 3724kb
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:
-1.2967420189 49999999999996.1218223572
result:
ok Point (-1.2967420, 49999999999996.1250000)
Test #13:
score: 0
Accepted
time: 2ms
memory: 3832kb
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.6771243449 -26.6300647928
result:
ok Point (-41.6771243, -26.6300648)
Test #14:
score: 0
Accepted
time: 2ms
memory: 3840kb
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:
-8.0140067739 42.4522515245
result:
ok Point (-8.0140068, 42.4522515)
Test #15:
score: 0
Accepted
time: 7ms
memory: 3696kb
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.8284271246 14.3309524420
result:
ok Point (43.8284271, 14.3309524)
Test #16:
score: 0
Accepted
time: 7ms
memory: 3844kb
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.9276278375 25.5823600625
result:
ok Point (16.9276278, 25.5823601)
Test #17:
score: 0
Accepted
time: 103ms
memory: 4404kb
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.0294117651 -33.1596020781
result:
ok Point (17.0294118, -33.1596021)
Test #18:
score: 0
Accepted
time: 118ms
memory: 4372kb
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.8340255830 -32.7876563672
result:
ok Point (-36.8340256, -32.7876564)
Test #19:
score: 0
Accepted
time: 0ms
memory: 3620kb
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:
30.0000000113 -40.0000000000
result:
ok Point (30.0000000, -40.0000000)
Test #20:
score: 0
Accepted
time: 2ms
memory: 3736kb
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:
19.0000001187 26.0000000000
result:
ok Point (19.0000001, 26.0000000)
Test #21:
score: 0
Accepted
time: 1ms
memory: 3824kb
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.0000000014 -8751.5000021573
result:
ok Point (-15.0000000, -8751.5000022)
Test #22:
score: 0
Accepted
time: 1ms
memory: 3728kb
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.9999999993 -8748.4999989285
result:
ok Point (-10.0000000, -8748.4999989)
Test #23:
score: 0
Accepted
time: 2ms
memory: 3656kb
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.0000000006 -12681.5000020158
result:
ok Point (-5.0000000, -12681.5000020)
Test #24:
score: 0
Accepted
time: 116ms
memory: 4376kb
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:
-12.0000000003 -12675.5000010844
result:
ok Point (-12.0000000, -12675.5000011)