QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#188572#7239. Triangleucup-team004AC ✓174ms3876kbC++201.7kb2023-09-26 01:38:252023-09-26 01:38:25

Judging History

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

  • [2023-09-26 01:38:25]
  • 评测
  • 测评结果:AC
  • 用时:174ms
  • 内存:3876kb
  • [2023-09-26 01:38:25]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 1E5;

void solve() {
    int n, c;
    std::cin >> n >> c;
    
    std::bitset<N + 1> a{}, b{};
    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;
        a[x] = b[N - x] = 1;
    }
    
    double ans = -1;
    
    std::vector<int> lst(2 * c + 1);
    for (int i = 1; i <= 2 * c; i++) {
        lst[i] = i <= N && a[i] ? i : lst[i - 1];
    }
    
    for (int s = 2 * c; s >= 3; s--) {
        int z = lst[s - 1];
        if (2 * z >= s) {
            auto v = a & (s < N ? b >> (N - s) : b << (s - N));
            int x = v._Find_next(s - z);
            int y = s - x;
            if (x < y && y < z) {
                double p = 0.5 * (x + y + z);
                double area = std::sqrt(p * (p - x) * (p - y) * (p - z));
                if (ans < 0 || ans > area) {
                    ans = area;
                }
            }
        }
    }
    for (int z = 1; z <= c; z++) {
        if (a[z]) {
            int y = lst[z - 1];
            if (!y) {
                continue;
            }
            int x = a._Find_next(z - y);
            if (x < y) {
                double p = 0.5 * (x + y + z);
                double area = std::sqrt(p * (p - x) * (p - y) * (p - z));
                if (ans < 0 || ans > area) {
                    ans = area;
                }
            }
        }
    }
    
    std::cout << ans << "\n";
}

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

詳細信息

Test #1:

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

input:

4
3 3
1 2 3
4 4
1 2 3 4
3 11
5 7 11
6 11
5 7 8 9 10 11

output:

-1.0000000000
2.9047375097
12.9687123493
12.9687123493

result:

ok 4 numbers

Test #2:

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

input:

20
5 20
15 20 11 17 18
5 20
12 18 13 20 15
5 20
12 10 14 18 16
5 20
18 16 15 11 14
5 20
18 12 11 20 14
5 20
20 15 10 16 12
5 20
12 10 15 13 17
5 20
18 15 13 20 12
5 20
16 18 20 10 14
5 20
11 15 16 13 18
5 20
11 13 16 14 17
5 20
20 14 11 13 16
5 20
16 11 15 13 18
5 20
11 15 13 20 14
5 20
16 10 13 20 ...

output:

81.2599993847
74.8331477355
56.5685424949
73.4846922835
56.7180526817
45.5960524607
56.9950655759
74.8331477355
64.9923072371
69.6289271783
67.5277720645
66.0000000000
69.6289271783
66.0000000000
31.9755766172
85.4513750621
56.1465715783
67.5277720645
42.4264068712
82.6498638837

result:

ok 20 numbers

Test #3:

score: 0
Accepted
time: 102ms
memory: 3856kb

input:

5000
4 20
11 14 16 17
4 20
13 19 10 15
4 20
19 12 16 14
4 20
11 13 10 15
4 20
17 15 14 18
4 20
14 12 19 15
4 20
13 17 19 11
4 20
16 20 12 18
4 20
20 19 12 16
4 20
14 15 18 17
4 20
16 11 12 15
4 20
10 17 16 19
4 20
17 19 18 13
4 20
11 18 15 20
4 20
19 11 10 16
4 20
18 20 15 11
4 20
17 20 10 15
4 20
1...

output:

75.4747474325
60.7947366143
81.3326502704
53.4415568635
99.6794863550
78.9267856941
69.2617318582
94.1010095589
95.5035994086
99.6794863550
65.2380257212
78.2268336314
105.2995726487
81.3879597975
42.4264068712
81.3879597975
72.6184377414
85.4513750621
52.3873792053
52.3873792053
64.0624695122
72.61...

result:

ok 5000 numbers

Test #4:

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

input:

3333
5 30
8 19 7 14 24
5 30
22 29 9 26 21
5 30
27 16 13 10 29
5 30
14 6 25 28 22
5 30
23 19 13 14 21
5 30
24 9 28 30 5
5 30
20 19 23 5 11
5 30
30 7 25 23 11
5 30
22 24 21 15 26
5 30
26 5 28 12 24
5 30
8 23 7 29 14
5 30
29 13 20 24 11
5 30
27 25 13 18 22
5 30
25 27 23 7 18
5 30
16 20 9 12 7
5 30
24 1...

output:

18.7999335105
50.6970166775
64.9186991552
60.5552433733
81.2403840464
38.8192928838
31.2759891930
66.8131723540
150.7846145998
38.8192928838
18.7999335105
66.0000000000
101.0346475225
49.4772675074
31.3049516850
41.2310562562
26.6634112596
26.9060866720
21.3307290077
51.9615242271
23.5252523897
25.9...

result:

ok 3333 numbers

Test #5:

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

input:

500
6 200
173 127 108 151 145 182
6 200
178 189 113 127 187 158
6 200
141 161 181 111 107 167
6 200
140 137 190 184 153 155
6 200
186 195 145 133 198 106
6 200
192 116 185 143 150 111
6 200
145 111 159 109 182 176
6 200
135 119 108 140 172 143
6 200
173 175 145 170 127 117
6 200
165 114 171 100 129 ...

output:

6645.9987962683
6969.8075430746
5496.6719192162
8830.6568272128
6563.9002077652
5810.7870325370
5623.2837381729
6138.6868302594
7096.8420573872
5474.1093739073
6870.0584740961
9145.7953966563
6860.7963049124
7405.5144318271
11535.3543508641
7028.1482758619
9446.6368188631
4624.9511821748
8656.402020...

result:

ok 500 numbers

Test #6:

score: 0
Accepted
time: 101ms
memory: 3716kb

input:

50
100 2000
1677 1203 1583 1791 1148 1678 1432 1149 1879 1528 1093 1165 1050 1499 1572 1580 1795 1300 1513 1355 1426 1670 1820 1706 1758 1739 1672 1654 1561 1730 1644 1393 1102 1285 1007 1454 1298 1295 1011 1870 1170 1489 1200 1555 1663 1518 1812 1529 1874 1891 1107 1906 1328 1478 1952 1809 1829 103...

output:

209032.2629456695
226587.6011975004
209805.5292407710
129975.3705599161
132857.5855229953
140184.6906762646
145289.5816926923
225363.2950885913
77517.7011462543
151749.5676309738
220880.8971741049
157302.8940998464
137852.7754052761
208551.9064885286
217077.5433720344
141030.5986656796
210407.043703...

result:

ok 50 numbers

Test #7:

score: 0
Accepted
time: 125ms
memory: 3832kb

input:

25
100 4000
3241 3656 1196 3385 1954 2733 2284 2502 1607 2447 2321 2868 3633 2093 1484 1069 3062 2314 2552 3949 2971 2921 2569 3766 2698 1805 1251 1674 1901 2642 3001 3637 2633 3585 1074 2536 1440 3350 3293 2259 1684 1997 2450 1881 1940 2663 2489 3361 3760 2876 3550 1702 3864 2160 3427 2185 2935 232...

output:

39148.7641687129
40343.6031290897
33737.4058196166
35980.4971781589
50337.0996724831
34066.5264730277
34517.4106385097
40955.9756346678
44911.6285213251
35397.7867943393
38620.3679932947
44234.2515725936
37309.6601356472
43090.9879462922
45514.6849866886
41665.5180987528
36545.0233607464
40751.20007...

result:

ok 25 numbers

Test #8:

score: 0
Accepted
time: 110ms
memory: 3808kb

input:

10
1000 10000
3747 2825 6947 9593 4913 4789 6876 8658 5587 3815 9608 5398 4603 4228 1308 2340 6149 7926 5053 7058 5076 6884 7177 7285 1511 8570 8463 4515 8533 5915 3139 8267 1292 4938 4449 8903 1791 3967 5632 5144 6954 2931 1643 2328 4310 7968 3616 8010 7464 1254 1542 2334 4730 9394 8169 8563 2413 5...

output:

32556.2127740236
32793.3632529129
34264.4470287717
32124.2102539113
32747.0013274116
32411.8765182996
32838.3913763677
32769.9330322401
32843.2638784196
31911.1063884896

result:

ok 10 numbers

Test #9:

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

input:

5
10000 20000
816 7176 11720 19404 2630 12346 12080 6785 12785 7300 585 5996 13354 17594 8322 11897 3679 11553 15700 1103 1789 13177 8348 15058 11351 17220 1793 1319 17367 234 17048 18863 3653 4907 18745 10842 7472 13921 5298 17055 9488 16642 18727 8648 17062 17935 12936 9216 9879 3109 16775 5258 12...

output:

9.9215674165
17.6050418915
9.7979589711
8.7856416954
11.6592238164

result:

ok 5 numbers

Test #10:

score: 0
Accepted
time: 139ms
memory: 3808kb

input:

1
50000 100000
26139 26949 70486 12878 81550 21532 41164 20710 97617 91566 95003 39317 87645 61540 56856 77954 77545 78487 93963 60808 9315 31470 54923 71978 37885 47745 34827 73655 51098 44759 19084 15968 12119 71563 45113 27653 82972 24006 33790 36400 29897 38405 71973 61376 16378 58377 10483 4353...

output:

5.3326822519

result:

ok found '5.332682252', expected '5.332682252', error '0.000000000'

Test #11:

score: 0
Accepted
time: 138ms
memory: 3808kb

input:

1
50000 100000
74907 51418 92110 51191 97802 60679 86079 65117 77937 58169 57954 59000 81034 68864 63761 67056 67354 75390 69109 71430 96093 94749 77968 78911 96369 88694 88042 61376 62416 74366 53329 64597 73647 76952 83758 63370 58462 98302 80642 63048 92322 99304 84461 55499 89704 87614 83090 632...

output:

11180367.8377547096

result:

ok found '11180367.837754710', expected '11180367.837754710', error '0.000000000'

Test #12:

score: 0
Accepted
time: 159ms
memory: 3824kb

input:

1
50000 100000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...

output:

2.9047375097

result:

ok found '2.904737510', expected '2.904737510', error '0.000000000'

Test #13:

score: 0
Accepted
time: 136ms
memory: 3808kb

input:

1
50000 97665
68238 50149 54693 60263 68119 79725 88195 63519 97195 54258 61336 77325 47093 83823 54909 68491 85719 59985 73852 82715 95974 62976 67613 66068 81133 79959 85952 69086 94402 75126 97328 50712 77405 52389 78158 66248 61022 55786 76404 95569 86089 85874 80369 96182 91718 91804 67082 4816...

output:

10104302.6932959817

result:

ok found '10104302.693295982', expected '10104302.693295982', error '0.000000000'

Test #14:

score: 0
Accepted
time: 135ms
memory: 3824kb

input:

1
50000 100000
62745 71214 86675 86719 67793 58256 58526 74975 82274 80210 61085 96669 66852 78851 60763 61308 72967 56956 72103 78280 59928 57789 69154 85687 97136 66287 99452 93187 87237 64331 72866 51329 77604 85329 85061 51255 58171 84029 93713 90769 89332 81738 60831 67615 60449 64863 71131 732...

output:

11180367.8377547096

result:

ok found '11180367.837754710', expected '11180367.837754710', error '0.000000000'

Test #15:

score: 0
Accepted
time: 131ms
memory: 3808kb

input:

1
50000 100000
87968 86001 87541 76178 89307 79707 70946 91198 72588 83875 84838 81929 83569 68882 55794 97716 93054 91359 92686 79725 78983 57846 75052 51408 97397 72424 79645 54498 62914 56777 50986 85891 86011 70748 81612 91562 71827 80017 67919 92722 59162 70904 85425 84618 90730 58292 61784 650...

output:

11180367.8377547096

result:

ok found '11180367.837754710', expected '11180367.837754710', error '0.000000000'

Test #16:

score: 0
Accepted
time: 149ms
memory: 3868kb

input:

1
24993 100000
49999 49998 49997 49996 49995 49994 49993 49992 49991 49990 49989 49988 49987 49986 49985 49984 49983 49982 49981 49980 49979 49978 49977 49976 49975 49974 49973 49972 49971 49970 49969 49968 49967 49966 49965 49964 49963 49962 49961 49960 49959 49958 49957 49956 49955 49954 49953 499...

output:

11180367.8377547096

result:

ok found '11180367.837754710', expected '11180367.837754710', error '0.000000000'

Test #17:

score: 0
Accepted
time: 142ms
memory: 3812kb

input:

1
49993 100000
33332 33331 33330 33329 33328 33327 33326 33325 33324 33323 33322 33321 33320 33319 33318 33317 33316 33315 33314 33313 33312 33311 33310 33309 33308 33307 33306 33305 33304 33303 33302 33301 33300 33299 33298 33297 33296 33295 33294 33293 33292 33291 33290 33289 33288 33287 33286 332...

output:

6085737.7285688166

result:

ok found '6085737.728568817', expected '6085737.728568817', error '0.000000000'

Test #18:

score: 0
Accepted
time: 174ms
memory: 3876kb

input:

1
3001 100000
90000 90010 90020 90030 90040 90050 90060 90070 90080 90090 90100 90110 90120 90130 90140 90150 90160 90170 90180 90190 90200 90210 90220 90230 90240 90250 90260 90270 90280 90290 90300 90310 90320 90330 90340 90350 90360 90370 90380 90390 90400 90410 90420 90430 90440 90450 90460 9047...

output:

9624909.1650921535

result:

ok found '9624909.165092153', expected '9624909.165092153', error '0.000000000'

Test #19:

score: 0
Accepted
time: 159ms
memory: 3868kb

input:

1
6001 100000
90000 90005 90010 90015 90020 90025 90030 90035 90040 90045 90050 90055 90060 90065 90070 90075 90080 90085 90090 90095 90100 90105 90110 90115 90120 90125 90130 90135 90140 90145 90150 90155 90160 90165 90170 90175 90180 90185 90190 90195 90200 90205 90210 90215 90220 90225 90230 9023...

output:

9624477.5204946157

result:

ok found '9624477.520494616', expected '9624477.520494616', error '0.000000000'

Test #20:

score: 0
Accepted
time: 156ms
memory: 3868kb

input:

1
9001 100000
85000 85005 85010 85015 85020 85025 85030 85035 85040 85045 85050 85055 85060 85065 85070 85075 85080 85085 85090 85095 85100 85105 85110 85115 85120 85125 85130 85135 85140 85145 85150 85155 85160 85165 85170 85175 85180 85185 85190 85195 85200 85205 85210 85215 85220 85225 85230 8523...

output:

9647833.1648228765

result:

ok found '9647833.164822876', expected '9647833.164822876', error '0.000000000'

Test #21:

score: 0
Accepted
time: 165ms
memory: 3876kb

input:

1
2251 100000
85000 85020 85040 85060 85080 85100 85120 85140 85160 85180 85200 85220 85240 85260 85280 85300 85320 85340 85360 85380 85400 85420 85440 85460 85480 85500 85520 85540 85560 85580 85600 85620 85640 85660 85680 85700 85720 85740 85760 85780 85800 85820 85840 85860 85880 85900 85920 8594...

output:

9094171.6444228683

result:

ok found '9094171.644422868', expected '9094171.644422868', error '0.000000000'