QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#331329#7261. StainsPetroTarnavskyiAC ✓27ms5596kbC++202.0kb2024-02-18 05:22:452024-02-18 05:22:46

Judging History

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

  • [2024-02-18 05:22:46]
  • 评测
  • 测评结果:AC
  • 用时:27ms
  • 内存:5596kb
  • [2024-02-18 05:22:45]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); 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;
/**
 * Description: $n = am + b, \frac{n}{m} = a, n \% m = b$.
 * use \_\_gcd instead of gcd.\\
 */
LL closest(LL u, LL d)
{
	if(d < 0)
		return closest(-u, -d);
	if(u < 0)
		return -closest(-u, d);
	return (2 * u + d) / (2 * d);
}
struct num : complex<LL>
{	
	num(LL a, LL b = 0) : complex(a, b) {}
	num(complex a) : complex(a) {}
	num operator/ (num x)
	{
		num prod = *this * conj(x);
		LL D = (x * conj(x)).real();
		
		LL m = closest(prod.real(), D);
		LL n = closest(prod.imag(), D);
	
		return num(m, n);
	}
	num operator% (num x)
	{
		return *this - x * (*this / x);
	}
	bool operator == (num b)
	{
		FOR(it, 0, 4)
		{
			if(real() == b.real() && imag() == b.imag())
				return true;
			b = b * num(0, 1);
		}
		return false;
	}
	bool operator != (num b)
	{
		return !(*this == b);
	}
};



//a + bi = I * (c + di) + J * (-d + ci)
//a = Ic - Jd
//b = Id + Jc
//ac = Ic^2 - Jcd
//bd = Id^2 + Jcd
//ac + bd = I * (c ^ 2 + d^2)

//(I, J) = (a + bi) / (c + di)




int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);
	cout << fixed << setprecision(15);
	
	int n;
	cin >> n;
	vector<num> a(n, 0);
	num g = 0;
	FOR(i, 0, n)
	{
		int A, B;
		cin >> A >> B;
		a[i] = num(A, B);
		if(i != 0)
		{
			a[i] -= a[0];
			g = __gcd(g, a[i]);
		}
	}
	vector<int> Is(n), Js(n);
	FOR(i, 1, n)
	{
		auto res = a[i] / g;
		Is[i] = res.real();
		Js[i] = res.imag();
	}
		
	sort(ALL(Is));
	sort(ALL(Js));
	
	LL k = max(Is.back() - Is[0] + 1, Js.back() - Js[0] + 1);
	cout << k * k - n << "\n";
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3612kb

input:

3
1 5
3 6
4 9

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

3
602436426 24979445
129527555 152215772
380195505 813284654

output:

255300871225040353

result:

ok 1 number(s): "255300871225040353"

Test #3:

score: 0
Accepted
time: 27ms
memory: 5572kb

input:

100000
880895728 923078537
523643950 773682958
29852782 726887397
327136772 729973312
417414167 39802442
930004355 187934454
694311625 655296752
717006914 566993343
353932878 269423539
732467709 187832264
445080754 97844
398614077 834130583
441160824 444432962
146276596 50224029
536891929 770030825
...

output:

999950336616528224

result:

ok 1 number(s): "999950336616528224"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

3
370575252 770089653
506257205 722368932
674132284 73852789

output:

31867732684837446

result:

ok 1 number(s): "31867732684837446"

Test #5:

score: 0
Accepted
time: 26ms
memory: 5516kb

input:

100000
521922260 6054011
7020374 567815273
457349507 177232802
39093416 751899479
337935762 412398827
203242633 838574320
146696764 745256683
636334643 404347010
571241289 59870658
364285458 557950285
263687892 834678227
410351490 594643571
353964123 665481180
65715590 832580261
494075646 177643649
...

output:

114701445168236324

result:

ok 1 number(s): "114701445168236324"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

3
558112510 112979083
689990289 942112073
913022831 873426572

output:

2077777981022497

result:

ok 1 number(s): "2077777981022497"

Test #7:

score: 0
Accepted
time: 26ms
memory: 5592kb

input:

100000
36328371 852554490
987002062 358835070
830608939 619295376
999270744 247031439
112934524 760893762
519058073 880814696
857181597 309249193
995869467 211948018
506419643 707147282
596509626 787549312
828173813 284753181
367621515 510861441
145413529 647640977
156320731 891989393
910974948 2200...

output:

4795135513904889

result:

ok 1 number(s): "4795135513904889"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

3
438440875 694638152
602148637 704842539
545570589 318126837

output:

29598605011597

result:

ok 1 number(s): "29598605011597"

Test #9:

score: 0
Accepted
time: 26ms
memory: 5520kb

input:

100000
765488289 265369464
717612260 859093643
143667157 376603862
982034424 119935123
347212922 951293480
530612132 306167176
82132655 696758916
964613780 331831825
152046936 714254382
658499859 970652599
550194444 591679929
614875099 470659562
744144620 782439739
333838499 232177604
494118167 3698...

output:

407994591563376

result:

ok 1 number(s): "407994591563376"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

3
890601211 849762562
605999387 661255602
303657951 233821688

output:

73864089514081

result:

ok 1 number(s): "73864089514081"

Test #11:

score: 0
Accepted
time: 27ms
memory: 5420kb

input:

100000
656047157 723155586
905754497 882475876
215178289 754320642
270640953 754996982
943537247 521339300
258104253 504004420
491886711 507559716
480341159 985595686
50639003 633626846
573003909 166819752
883273335 731165390
592810423 854310254
811994717 388573164
513977851 111977810
30279641 55542...

output:

201045118505444

result:

ok 1 number(s): "201045118505444"

Test #12:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

3
532479135 802312680
383026733 250611794
10581891 880589538

output:

996357323326

result:

ok 1 number(s): "996357323326"

Test #13:

score: 0
Accepted
time: 23ms
memory: 5436kb

input:

100000
362987313 360404333
615962123 511756413
965946087 670787615
530840559 209621811
274493523 273867113
446371251 14958617
458124905 733156339
639106101 421399817
213706247 822575295
876384373 395738313
152078593 854263523
465236845 463934859
74112155 487215039
469915277 158090485
572863661 40698...

output:

2977453680900

result:

ok 1 number(s): "2977453680900"

Test #14:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

3
334342343 342772366
896665872 14576399
379427577 632722734

output:

41053243453

result:

ok 1 number(s): "41053243453"

Test #15:

score: 0
Accepted
time: 22ms
memory: 5424kb

input:

100000
163015047 994750493
24084514 561971872
330909048 543495260
345325100 250544374
180694813 423751205
649981546 49550406
324881388 816990500
563981869 369413387
242590986 862568996
402433129 456319477
248605069 752168427
416843601 611173351
280876834 766446712
403500028 197876730
59403047 484695...

output:

108304077216

result:

ok 1 number(s): "108304077216"

Test #16:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

3
998821231 676932324
272357182 590769365
946624815 705937945

output:

2479641613

result:

ok 1 number(s): "2479641613"

Test #17:

score: 0
Accepted
time: 26ms
memory: 5576kb

input:

100000
755702347 281968311
825247335 269066426
896072815 954874378
455781935 257909157
738662792 60156923
532564207 672478385
761007556 321448287
642425597 604099562
593548209 256069140
637613302 822615066
753458927 697332903
729208287 109987839
966249924 259822254
769881088 758093939
736098655 9524...

output:

7406395721

result:

ok 1 number(s): "7406395721"

Test #18:

score: 0
Accepted
time: 0ms
memory: 3528kb

input:

3
29225426 356138255
284125635 389556472
707559815 841117504

output:

6220033

result:

ok 1 number(s): "6220033"

Test #19:

score: 0
Accepted
time: 27ms
memory: 5468kb

input:

100000
162269213 515848588
336555602 545387061
599469995 715539291
651265899 526610582
28729406 341539760
516409986 617055411
912355589 867064224
863476777 420817603
32646747 464060210
991110031 481037546
721731009 85309290
362800074 653820721
547371690 896211099
281485658 757692541
637999549 794161...

output:

395352996

result:

ok 1 number(s): "395352996"

Test #20:

score: 0
Accepted
time: 0ms
memory: 3524kb

input:

3
690159823 248831820
196071252 836829317
630544210 921371411

output:

311361

result:

ok 1 number(s): "311361"

Test #21:

score: 0
Accepted
time: 24ms
memory: 5596kb

input:

100000
507726724 878832229
323614270 21858897
189187050 708963803
991409816 603764215
514797538 80566623
378393205 324817558
451255781 286822598
303241859 988765488
157040214 776180017
535629754 152948805
952369694 551854857
918222871 508191352
820598374 678155153
668107305 139970206
687998163 36533...

output:

29700681

result:

ok 1 number(s): "29700681"

Test #22:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

3
40057493 123460374
850402613 568597464
872769893 571002924

output:

1974022

result:

ok 1 number(s): "1974022"

Test #23:

score: 0
Accepted
time: 23ms
memory: 5428kb

input:

100000
35009333 642532790
90561023 479375870
263248193 342987560
320150303 294555080
836301953 34548380
350113493 516830660
519934793 836478260
694120073 940722470
616268513 985170800
990089483 285036590
97659323 796339220
217063733 775805090
210993983 808286090
383194703 869963630
809188853 6658844...

output:

2813849

result:

ok 1 number(s): "2813849"

Test #24:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

3
463690546 747005237
787952632 658917860
938378614 909503798

output:

20733

result:

ok 1 number(s): "20733"

Test #25:

score: 0
Accepted
time: 22ms
memory: 5572kb

input:

100000
232963401 585171286
967360332 314130343
126573267 777889435
339446559 818505046
188291004 397286185
873580839 132025273
354411531 868533226
826186416 583287892
575222919 61427920
829586217 300314083
290929323 989194876
406851303 60956983
557644626 514253281
874734660 554615365
544811466 92687...

output:

178784

result:

ok 1 number(s): "178784"

Test #26:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

3
632405220 747731085
687111312 938556941
119182922 700743523

output:

286

result:

ok 1 number(s): "286"

Test #27:

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

input:

4975
864977677 664946865
552471929 35884785
667474926 876448872
863789170 250204422
235519428 839205132
71797321 404975045
75803458 310897496
268360862 363079702
860326074 36427826
913696787 258612865
250208597 494254119
844697695 550985503
150246491 923538859
367090014 995604878
579135062 885253484...

output:

3861

result:

ok 1 number(s): "3861"

Test #28:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

3
975129587 963048662
708903358 391697135
686378450 606722801

output:

22

result:

ok 1 number(s): "22"

Test #29:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

423
218177019 813668965
512455479 909711536
880251602 926501313
246437058 751413756
25468453 163064644
115983701 129069474
512039863 83604042
93666601 757148887
699221106 994491653
132981286 174327098
36938715 468605558
348214760 609905753
936563872 388937148
585973142 830458742
755325568 43873741
8...

output:

306

result:

ok 1 number(s): "306"

Test #30:

score: 0
Accepted
time: 0ms
memory: 3676kb

input:

3
807266052 913017179
113895236 703355187
336434196 467939259

output:

6

result:

ok 1 number(s): "6"

Test #31:

score: 0
Accepted
time: 0ms
memory: 3528kb

input:

5
301137964 823414746
288260996 365459858
65722036 600875786
52845068 142920898
510799956 130043930

output:

4

result:

ok 1 number(s): "4"