QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#188572 | #7239. Triangle | ucup-team004 | AC ✓ | 174ms | 3876kb | C++20 | 1.7kb | 2023-09-26 01:38:25 | 2023-09-26 01:38:25 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'