QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#345982#3196. Bribing EvePetroTarnavskyi#AC ✓45ms8248kbC++202.5kb2024-03-07 18:53:242024-03-07 18:53:24

Judging History

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

  • [2024-03-07 18:53:24]
  • 评测
  • 测评结果:AC
  • 用时:45ms
  • 内存:8248kb
  • [2024-03-07 18:53:24]
  • 提交

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'