QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#345982 | #3196. Bribing Eve | PetroTarnavskyi# | AC ✓ | 45ms | 8248kb | C++20 | 2.5kb | 2024-03-07 18:53:24 | 2024-03-07 18:53:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
struct Pt
{
int x, y;
Pt operator-(const Pt& p) const
{
return {x - p.x, y - p.y};
}
};
int sq(const Pt& p)
{
return p.x * p.x + p.y * p.y;
}
int sgn(int x)
{
return (0 < x) - (x < 0);
}
Pt perp(const Pt& p)
{
return {-p.y, p.x};
}
int dot(const Pt& p, const Pt& q)
{
return p.x * q.x + p.y * q.y;
}
int cross(const Pt& p, const Pt& q)
{
return p.x * q.y - p.y * q.x;
}
int orient(const Pt& p, const Pt& q, const Pt& r)
{
return cross(q - p, r - p);
}
bool half(const Pt& p)
{
assert(sgn(p.x) != 0 || sgn(p.y) != 0);
return sgn(p.y) == -1 ||
(sgn(p.y) == 0 && sgn(p.x) == -1);
}
void polarSortAround(const Pt& o, vector<pair<Pt, int>>& v)
{
sort(ALL(v), [o](pair<Pt, int> pp, pair<Pt, int> qq)
{
Pt p = pp.F - o, q = qq.F - o;
bool hp = half(p), hq = half(q);
if (hp != hq)
return hp < hq;
int s = sgn(cross(p, q));
if (s != 0)
return s == 1;
return sq(p) < sq(q);
});
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
Pt o;
cin >> o.x >> o.y;
vector<pair<Pt, int>> v;
int cntEq = 0;
FOR(i, 1, n)
{
Pt p;
cin >> p.x >> p.y;
p = p - o;
if (p.x == 0 && p.y == 0)
cntEq++;
else
{
v.PB({p, 1});
v.PB({{-p.x, -p.y}, 0});
}
}
v.PB({{1, 0}, 0});
v.PB({{0, 1}, 0});
v.PB({{-1, 0}, 0});
v.PB({{0, -1}, 0});
for (auto& [p, c] : v)
p = perp(p);
polarSortAround({0, 0}, v);
n = SZ(v);
VI pref(3 * n + 47);
FOR(i, 0, SZ(pref) - 1)
pref[i + 1] = pref[i] + v[i % n].S;
int st = -1;
int mn = n + 47, mx = 0;
int ptr1 = 0, ptr2 = 0, ptr3 = 0;
FOR(i, 0, n)
{
Pt p = v[i].F;
if (p.x < 0 || p.y < 0)
break;
ptr1 = max(ptr1, st + i);
while (cross(p, v[ptr1 % n].F) == 0 && dot(p, v[ptr1 % n].F) > 0 && ptr1 < n + i)
ptr1++;
ptr2 = max(ptr2, ptr1);
while (cross(p, v[ptr2 % n].F) > 0)
ptr2++;
ptr3 = max(ptr3, ptr2);
while (cross(p, v[ptr3 % n].F) == 0 && dot(p, v[ptr3 % n].F) < 0)
ptr3++;
mn = min(mn, pref[ptr2] - pref[ptr1]);
mx = max(mx, pref[ptr3] - pref[i]);
}
mx += cntEq;
cout << mn + 1 << " " << mx + 1 << "\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3620kb
input:
5 7 7 11 10 8 5 1 1 12 12
output:
3 4
result:
ok single line: '3 4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
1 500 500
output:
1 1
result:
ok single line: '1 1'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
19 4 5 3 4 6 7 1 8 9 2 3 7 9 3 2 3 1 2 4 5 3 7 9 3 2 3 1 2 4 5 3 5 6 1 1 6 8 1
output:
5 11
result:
ok single line: '5 11'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
10 500 500 501 501 501 502 1 500 499 500 499 500 2 500 600 500 1000 500 700 500
output:
3 10
result:
ok single line: '3 10'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
4 2 2 2 3 3 2 3 2
output:
2 4
result:
ok single line: '2 4'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
13 24 4 6 11 17 6 19 9 3 12 13 8 14 7 24 3 21 5 22 5 27 3 31 2 32 1
output:
4 10
result:
ok single line: '4 10'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
11 8 21 4 24 11 6 6 17 9 19 8 13 7 14 5 2 10 2 2 31 110 3
output:
2 6
result:
ok single line: '2 6'
Test #8:
score: 0
Accepted
time: 39ms
memory: 7948kb
input:
100000 784 39 263 943 28 305 170 914 332 30 56 1 24 276 542 144 704 568 320 775 340 898 545 564 597 210 347 324 498 200 603 32 408 785 364 772 226 286 534 123 856 70 179 838 71 555 214 379 317 482 616 242 127 444 264 363 393 274 246 483 545 509 485 254 280 419 323 14 926 126 238 601 49 942 708 593 1...
output:
21573 96201
result:
ok single line: '21573 96201'
Test #9:
score: 0
Accepted
time: 40ms
memory: 7812kb
input:
100000 437 352 680 400 8 517 56 864 229 873 673 858 370 258 71 674 288 540 156 436 357 344 776 859 110 609 801 378 401 268 610 522 928 969 775 17 449 778 22 867 395 430 553 896 932 19 128 314 77 206 500 185 287 520 390 36 646 247 734 526 123 957 616 755 720 169 912 30 125 857 70 800 983 633 117 567 ...
output:
56206 69370
result:
ok single line: '56206 69370'
Test #10:
score: 0
Accepted
time: 39ms
memory: 8064kb
input:
100000 195 411 605 301 796 699 674 986 304 168 439 129 586 188 937 422 585 15 864 566 693 451 164 70 594 715 291 631 280 100 885 454 892 29 436 26 199 379 259 23 545 445 145 279 298 95 58 664 565 777 307 369 409 607 416 662 525 116 883 178 695 119 427 900 633 72 823 451 616 292 701 707 642 131 676 5...
output:
59016 84129
result:
ok single line: '59016 84129'
Test #11:
score: 0
Accepted
time: 44ms
memory: 7768kb
input:
100000 197 411 177 790 398 329 293 227 319 375 155 417 522 245 62 973 453 376 154 835 536 187 866 77 188 551 323 403 298 345 395 92 573 227 556 325 302 357 421 111 307 317 927 5 229 11 95 453 110 461 378 191 850 3 207 133 8 975 481 152 361 81 427 138 371 185 725 308 515 203 204 109 685 277 71 438 37...
output:
22411 77614
result:
ok single line: '22411 77614'
Test #12:
score: 0
Accepted
time: 44ms
memory: 7932kb
input:
100000 501 407 435 607 563 235 593 263 597 190 206 855 801 7 76 835 416 661 478 593 221 889 677 56 537 346 601 152 487 684 616 59 523 88 193 732 242 709 27 413 437 651 675 233 95 576 968 181 76 417 858 367 451 570 529 272 296 857 865 292 17 437 512 363 850 157 778 309 743 36 697 371 771 230 692 261 ...
output:
38167 61835
result:
ok single line: '38167 61835'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
1000 509 449 714 354 619 292 105 638 626 326 159 636 871 350 832 356 335 584 437 459 138 590 97 504 583 334 454 532 417 681 898 438 378 546 254 540 195 567 287 526 278 542 708 416 11 497 430 506 293 539 367 568 639 446 259 474 467 576 343 671 605 436 449 475 389 586 109 498 335 610 717 435 917 336 6...
output:
468 529
result:
ok single line: '468 529'
Test #14:
score: 0
Accepted
time: 40ms
memory: 7988kb
input:
100000 509 449 826 241 426 583 790 287 592 411 11 663 585 324 659 254 726 212 957 164 801 209 353 682 562 421 208 491 433 528 983 370 656 299 832 408 386 688 179 691 703 419 393 498 526 196 646 347 168 486 497 465 735 205 707 380 240 699 763 247 587 419 533 368 283 548 847 381 881 427 512 324 15 678...
output:
48885 50969
result:
ok single line: '48885 50969'
Test #15:
score: 0
Accepted
time: 45ms
memory: 8248kb
input:
100000 509 559 153 684 738 440 960 372 400 704 840 421 833 342 446 767 488 775 723 353 531 519 179 611 725 557 81 610 257 591 120 756 578 420 443 716 897 486 354 647 923 486 894 515 853 393 626 452 543 526 656 398 467 718 279 750 740 497 240 629 471 751 484 594 476 727 175 588 803 543 532 525 688 50...
output:
48784 50855
result:
ok single line: '48784 50855'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3704kb
input:
1000 509 449 385 601 884 285 731 293 212 521 410 458 773 263 141 645 709 351 577 403 108 553 166 658 537 403 418 656 89 644 67 484 207 645 970 339 763 237 770 442 680 381 937 260 444 641 969 366 219 499 477 673 395 451 676 423 443 595 615 211 853 424 275 509 998 318 201 620 156 512 723 230 925 322 2...
output:
486 524
result:
ok single line: '486 524'
Test #17:
score: 0
Accepted
time: 36ms
memory: 7976kb
input:
100000 500 594 566 394 438 766 408 738 404 811 795 146 200 994 925 166 585 340 523 408 780 112 324 945 464 655 400 849 514 317 385 942 478 913 808 269 759 292 974 588 564 350 326 768 906 425 33 820 925 584 143 634 550 431 472 729 705 144 136 709 984 564 489 638 151 844 223 692 258 965 304 630 230 77...
output:
38166 61834
result:
ok single line: '38166 61834'
Test #18:
score: 0
Accepted
time: 43ms
memory: 8036kb
input:
100000 806 590 396 700 205 302 327 15 697 833 562 872 415 813 64 579 416 986 137 435 308 550 837 931 407 286 710 370 721 901 116 547 109 972 565 975 802 622 742 978 456 556 856 722 703 906 943 337 436 224 694 632 592 394 585 339 476 885 118 823 306 882 574 101 368 929 178 550 385 709 300 294 359 870...
output:
15872 40985
result:
ok single line: '15872 40985'
Test #19:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
1000 492 552 616 400 117 716 270 708 789 480 591 543 228 738 860 356 292 650 424 598 893 448 835 343 464 598 583 345 912 357 934 517 794 356 31 662 238 764 231 559 321 620 64 741 557 360 32 635 782 502 524 328 606 550 325 578 558 406 386 790 148 577 726 492 3 683 800 381 845 489 278 771 76 679 791 4...
output:
477 515
result:
ok single line: '477 515'