QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#391238 | #8550. All the Way Left | 5ab | AC ✓ | 335ms | 3996kb | C++20 | 2.3kb | 2024-04-16 14:58:22 | 2024-04-16 14:58:22 |
Judging History
answer
/* name: std
* author: 5ab
* created at: 2023-11-24
*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define ssz(x) (int((x).size()))
auto chmax = [](auto& x, auto y) { if (x < y) x = y; };
auto chmin = [](auto& x, auto y) { if (y < x) x = y; };
using ll = long long;
using ld = long double;
const int max_n = 3000;
struct point
{
int x, y;
point operator-(const point& rhs) const {
return { x - rhs.x, y - rhs.y };
}
bool operator<(const point& rhs) const {
return x == rhs.x ? y < rhs.y : x < rhs.x;
}
bool operator==(const point& rhs) const = default;
}
a[max_n];
ll dot(const point& x, const point& y) {
return 1ll * x.x * y.x + 1ll * x.y * y.y;
}
ll cross(const point& x, const point& y) {
return 1ll * x.x * y.y - 1ll * x.y * y.x;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int cas, n;
cin >> cas;
while (cas--)
{
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i].x >> a[i].y;
swap(a[0], *min_element(a, a + n));
sort(a + 1, a + n, [&](const auto& p, const auto& q) {
ll x = cross(p - a[0], q - a[0]);
return x != 0 ? x > 0 : dot(p - a[0], q - p) > 0;
// return x > 0;
});
if (n <= 2 || cross(a[1] - a[0], a[n - 1] - a[0]) == 0)
{
cout << (n == 1 ? 1 : 2) << "\n";
continue;
}
vector<point> cv, res;
for (int i = 0; i < n; i++)
{
while (ssz(cv) > 1 && cross(a[i] - cv.back(), cv.back() - cv.end()[-2]) > 0)
cv.pop_back();
cv.push_back(a[i]);
}
for (int i = n - 2; cross(a[n - 1] - a[i], a[i] - a[0]) == 0; i--)
cv.push_back(a[i]);
sort(a, a + n), sort(all(cv));
for (int i = 0, j = 0; i < n; i++)
{
if (j < ssz(cv) && a[i] == cv[j])
j++;
else
res.push_back(a[i]);
}
int ans = 0;
vector<pair<int, ld>> cd;
cd.reserve(ssz(res));
for (int i = 0; i < n; i++)
{
cd.clear();
for (int j = 0; j < ssz(res); j++) if (res[j] != a[i])
{
auto d = res[j] - a[i];
cd.emplace_back(d.x > 0 || (d.x == 0 && d.y > 0), d.y / ld(d.x));
}
sort(all(cd));
ans += unique(all(cd)) - cd.begin();
}
cout << ans + ssz(cv) << "\n";
}
return 0;
}
// started coding at: 11-24 09:44:44
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3588kb
input:
3 4 1 1 3 1 2 2 2 3 3 1 1 1 2 1 3 6 1 1 2 1 2 2 2 3 3 2 4 2
output:
6 2 13
result:
ok 3 number(s): "6 2 13"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
15 1 1 1 2 1 1 1 2 3 1 1 1 2 1 3 3 1 1 1 2 2 2 5 1 1 1 3 2 2 3 1 3 3 6 1 1 1 3 2 2 3 2 4 1 4 3 6 1 3 2 1 2 2 2 3 2 4 3 2 6 1 1 5 1 3 5 2 2 4 2 3 3 7 1 1 5 1 2 2 3 2 4 2 3 3 3 4 6 2 10 8 9 2 3 2 5 3 5 2 6 10 1 10 7 6 8 4 3 8 6 9 3 7 6 8 8 5 10 9 8 8 8 1 1 2 3 2 4 1 6 5 3 5 4 6 1 6 6 8 1 1 2 3 3 3 4 2...
output:
1 2 2 3 8 14 12 16 22 10 54 32 28 10 14
result:
ok 15 numbers
Test #3:
score: 0
Accepted
time: 8ms
memory: 3668kb
input:
10000 7 999999994 1000000000 999999998 999999997 999999999 999999994 999999998 999999994 999999996 999999998 1000000000 999999994 1000000000 999999997 6 999999998 5 999999998 6 999999994 5 999999994 1 999999998 4 999999995 5 7 2 2 3 6 7 5 3 5 2 4 7 4 6 2 3 77279810 642022026 309119240 107003671 4636...
output:
17 10 12 3 2 4 2 21 5 12 2 1 4 3 17 1 3 16 2 5 10 1 4 1 4 8 1 17 4 12 2 2 16 3 4 6 3 17 2 5 2 3 4 21 5 4 6 4 17 2 10 12 2 10 5 4 1 1 4 2 8 15 5 10 10 4 12 2 4 2 12 1 4 1 10 1 4 14 2 2 5 8 1 17 1 3 8 2 2 16 13 4 10 2 12 12 1 2 21 2 5 8 3 12 2 17 3 4 17 10 1 12 1 5 8 8 10 1 8 8 4 3 4 5 12 5 1 1 4 2 2 ...
result:
ok 10000 numbers
Test #4:
score: 0
Accepted
time: 14ms
memory: 3548kb
input:
10000 10 1000000000 999999996 999999992 999999996 999999993 1000000000 999999996 999999998 999999992 999999991 999999996 999999999 999999993 999999993 999999991 999999995 999999995 999999997 999999998 999999997 9 999999995 1000000000 999999993 999999992 999999999 1000000000 999999998 999999999 99999...
output:
47 16 29 34 28 14 36 26 14 26 15 34 8 16 32 38 2 44 3 19 14 4 6 33 10 10 12 12 17 8 25 8 33 14 30 11 10 19 40 34 33 41 6 5 22 10 17 16 6 16 2 41 29 33 20 26 10 21 2 32 26 47 33 3 31 12 30 16 14 24 10 12 22 17 40 6 23 26 23 17 28 3 16 4 36 46 12 3 48 21 6 14 39 40 29 23 33 34 12 9 6 10 12 32 34 3 28 ...
result:
ok 10000 numbers
Test #5:
score: 0
Accepted
time: 121ms
memory: 3668kb
input:
10000 20 10 472423976 2 859313061 15 542767446 2 894484796 7 577939181 2 577939181 10 929656531 4 683454386 8 507595711 1 788969591 15 718626121 15 964828266 1 507595711 4 964828266 3 507595711 15 472423976 12 718626121 15 648282651 8 648282651 11 753797856 20 19 999999999 12 999999995 8 999999996 2...
output:
195 197 238 225 192 211 234 249 242 211 225 261 240 230 209 209 183 214 183 225 240 242 141 241 191 245 170 232 259 191 194 242 222 229 189 210 216 250 234 202 225 243 185 195 237 249 240 176 172 211 203 232 203 209 235 212 218 246 199 196 223 210 207 230 211 178 204 227 245 228 191 190 187 226 206 ...
result:
ok 10000 numbers
Test #6:
score: 0
Accepted
time: 125ms
memory: 3620kb
input:
10000 20 999999990 999999987 999999993 999999991 999999991 999999996 999999997 999999991 999999997 999999999 999999986 999999990 999999989 999999993 999999988 999999992 999999986 999999998 999999993 999999989 1000000000 999999994 999999995 999999988 999999991 999999989 999999994 999999994 999999996 ...
output:
250 208 219 215 216 224 160 224 185 209 186 231 205 210 209 248 189 198 224 233 221 232 216 213 221 230 203 213 208 242 201 227 254 210 206 246 239 246 172 213 223 205 218 232 194 228 230 208 247 209 238 245 224 251 234 214 221 256 231 245 240 228 158 213 242 231 192 232 221 208 190 232 208 247 229 ...
result:
ok 10000 numbers
Test #7:
score: 0
Accepted
time: 247ms
memory: 3972kb
input:
6 423 871052589 696370203 590606822 96125207 424963175 275218135 401552023 62808380 458556639 213160485 955603590 401616993 117520530 336079323 391036678 62821894 739838559 290358804 850343513 195705313 352952487 42119649 437338877 866366388 803885262 795778899 279023855 479705056 213974465 14674106...
output:
114514 1919810 1199282 974 26 1
result:
ok 6 numbers
Test #8:
score: 0
Accepted
time: 163ms
memory: 3928kb
input:
16 486 34060622 598468879 128647540 757780661 668466425 88271354 261524546 867470097 778177586 166231958 47339886 371835886 360942672 75140367 653090531 80941869 576631367 900830133 222375990 156853949 720877739 828175248 338270557 85134793 108934265 736556394 895297321 597692835 347786961 901398783...
output:
486 7442 6974 6402 113282 112138 121422 129176 272936 246268 273992 219769 265227 271284 229925 240937
result:
ok 16 numbers
Test #9:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
1 2000 368963 449991602 71690645 226469653 116119489 746924303 14456657 563523216 591696265 879438989 116209515 163496764 836456898 655094478 241619408 855832580 408694125 7058835 858105702 606589269 461893647 907489045 881686694 476771541 10299543 372869886 546580179 23973978 139944331 772781268 28...
output:
2000
result:
ok 1 number(s): "2000"
Test #10:
score: 0
Accepted
time: 2ms
memory: 3680kb
input:
1 2000 744286402 946400742 987763934 558344530 230642709 255584833 988354826 529569285 613631408 79006321 909007166 283642901 871800686 234872909 146697513 660667263 535381193 990122896 433983054 96440320 935182589 327092675 295229766 874996034 943116516 729567432 841158498 871565488 955381041 69966...
output:
29972
result:
ok 1 number(s): "29972"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
1 2000 769001450 754042265 25824918 578315923 195176522 830526044 660198770 102506141 176341551 814219275 361352592 56309147 860529759 319890700 143425404 781406087 826853273 258071284 452236374 42034217 857754231 612265458 870615679 346554880 366416325 54982850 132539126 199271969 320819767 6934938...
output:
29971
result:
ok 1 number(s): "29971"
Test #12:
score: 0
Accepted
time: 2ms
memory: 3940kb
input:
1 2000 92720650 320701832 868133136 724198785 701884285 873543357 132356020 684571482 523287572 31342492 396060735 44855451 949796867 494382726 833231382 768226875 943663059 423388738 896856813 680016197 505995366 30299910 520044988 913510433 254035248 816180553 586865276 42481991 156803847 21672662...
output:
39952
result:
ok 1 number(s): "39952"
Test #13:
score: 0
Accepted
time: 151ms
memory: 3892kb
input:
1 2000 921789228 394167112 67185499 569719790 684705345 738829782 360866636 555114318 846959948 713988184 113410674 337530338 935834181 437688129 251894406 879810056 97433362 685968840 899809289 344067418 832269999 246885813 381274629 252518169 826624109 240601626 495034793 888656585 313389757 52178...
output:
2007992
result:
ok 1 number(s): "2007992"
Test #14:
score: 0
Accepted
time: 151ms
memory: 3928kb
input:
1 2000 968352104 382682494 169810362 227039536 717966561 160707606 441686790 182476923 960722652 351321012 194467730 375514261 365912762 393135748 68576498 440778225 200672368 240077910 397172893 114006499 233424163 565208946 841069449 748138623 564685706 288340610 716483745 416169983 512789522 2061...
output:
1991245
result:
ok 1 number(s): "1991245"
Test #15:
score: 0
Accepted
time: 150ms
memory: 3736kb
input:
1 2000 339176530 362568555 954193274 419874680 511252289 988095198 90577325 572931848 521801976 138222296 235718442 856540834 689641989 940798368 163398420 342947025 908225644 338858057 931756216 559295464 596071112 194491827 892126869 413782835 334449675 192351238 199298090 299769065 957948062 6450...
output:
1992324
result:
ok 1 number(s): "1992324"
Test #16:
score: 0
Accepted
time: 149ms
memory: 3960kb
input:
1 2000 68023959 545355429 670976741 740016128 756274710 590394389 95885493 595690247 871395167 275123465 98557357 323741788 173795686 765626033 636750940 898363001 369796607 443301889 85748860 596231201 609909361 502550923 168226277 758782771 924672923 384159791 944148082 531941372 111732960 6502023...
output:
1984618
result:
ok 1 number(s): "1984618"
Test #17:
score: 0
Accepted
time: 328ms
memory: 3996kb
input:
1 2000 472317399 448095139 470057957 630422151 640572269 820742041 486621970 364956001 331756721 458127349 562088574 699893181 484360656 420118046 632196877 918382826 269387963 389598905 547430457 816036894 694837907 511061315 696696481 622416483 280660508 154457223 537659096 840781651 563474056 473...
output:
3974024
result:
ok 1 number(s): "3974024"
Test #18:
score: 0
Accepted
time: 324ms
memory: 3796kb
input:
1 2000 129892852 719880988 184919537 744105353 587102697 605473274 626545113 393257114 31249917 443389504 380359906 519791025 15047745 453844828 219382764 706338434 420710714 93495564 498185131 959746121 539399219 546379388 468794808 287432388 269897958 886528743 481025128 602157701 469331767 410256...
output:
3961204
result:
ok 1 number(s): "3961204"
Test #19:
score: 0
Accepted
time: 326ms
memory: 3756kb
input:
1 2000 510934899 547459563 519773921 365901465 496833202 515167890 654302266 231507260 733500503 460686130 432606988 77262088 25742008 636637521 134014773 686685517 379041620 252939972 681864072 251338397 855737338 246632327 309623668 229200708 692820865 277464076 288511703 248016522 286589348 51658...
output:
3964062
result:
ok 1 number(s): "3964062"
Test #20:
score: 0
Accepted
time: 335ms
memory: 3736kb
input:
1 2000 576715016 547277070 523392466 802721752 291730288 525334491 250099054 367469786 579560721 503865147 501420548 121382497 171360657 415872990 799343254 503750072 855064541 339988698 213016439 769254586 688291370 403587977 730744033 763739908 455349062 271922867 388474585 366824606 395462272 579...
output:
3950522
result:
ok 1 number(s): "3950522"
Test #21:
score: 0
Accepted
time: 326ms
memory: 3700kb
input:
1 2000 753399490 201420747 622181549 316348181 483137284 427471103 505501632 411398075 288945757 424009445 779719655 127660483 535994596 268390059 802466895 146833111 278458488 408398286 706788106 206012131 295405397 508692108 406905279 348331770 295353809 617182872 504337995 296574757 697746154 174...
output:
3992006
result:
ok 1 number(s): "3992006"
Test #22:
score: 0
Accepted
time: 326ms
memory: 3928kb
input:
1 2000 592736101 387284482 296073032 334186116 297857412 337555925 571732208 422401938 537700347 361036768 717213209 359576899 604927787 419384975 428138181 430955572 755558311 368389007 319563812 359681733 581471767 439734361 513676681 306659848 240266587 292815356 598054066 420025744 186430824 263...
output:
3991252
result:
ok 1 number(s): "3991252"
Test #23:
score: 0
Accepted
time: 322ms
memory: 3756kb
input:
1 2000 254482463 216326928 259688225 367860109 96889623 353950264 809227232 836951665 345354028 141005819 204570694 193377866 495650122 618254587 315571658 154789888 303782568 237636907 681975339 717893197 610887176 663410028 352777025 298763925 385694796 206052374 340672163 388607943 568842186 6266...
output:
3989972
result:
ok 1 number(s): "3989972"
Test #24:
score: 0
Accepted
time: 328ms
memory: 3800kb
input:
1 2000 662922115 221115958 587015717 182861841 732973227 202525759 610031685 182122157 600636621 175085573 356522102 591899596 675852703 207364274 374792496 523848515 541017593 394706666 639387965 189373958 717822245 235655806 604403003 326462818 495811759 360263663 576264288 181772296 418013709 605...
output:
3983682
result:
ok 1 number(s): "3983682"
Extra Test:
score: 0
Extra Test Passed