QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#141823#2140. Lots of ParabolasAs3b_team_f_masrAC ✓118ms4404kbC++141.5kb2023-08-18 02:22:442023-08-18 02:22:48

Judging History

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

  • [2023-08-18 02:22:48]
  • 评测
  • 测评结果:AC
  • 用时:118ms
  • 内存:4404kb
  • [2023-08-18 02:22:44]
  • 提交

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;
}

详细

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)