QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#324999 | #7261. Stains | PetroTarnavskyi | AC ✓ | 28ms | 5528kb | C++20 | 2.0kb | 2024-02-11 02:54:05 | 2024-02-11 02:54:08 |
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, 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 \rightarrow n / m = a, n \% m = b$\\
* New coordinates where x is
*/
LL closest(LL u, LL d)
{
if(u >= 0)
return (2 * u + d) / (2 * d);
return -closest(-u, d);
}
struct num : complex<LL>
{
num(LL a, LL b = 0) : complex(a, b) {}
num(complex a) : complex(a) {}
num inv()
{
return num(real(), -imag());
}
num operator/ (num x)
{
num prod = *this * x.inv();
LL D = (x * x.inv()).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;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3584kb
input:
3 1 5 3 6 4 9
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
3 602436426 24979445 129527555 152215772 380195505 813284654
output:
255300871225040353
result:
ok 1 number(s): "255300871225040353"
Test #3:
score: 0
Accepted
time: 23ms
memory: 5400kb
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: 3592kb
input:
3 370575252 770089653 506257205 722368932 674132284 73852789
output:
31867732684837446
result:
ok 1 number(s): "31867732684837446"
Test #5:
score: 0
Accepted
time: 27ms
memory: 5464kb
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: 3528kb
input:
3 558112510 112979083 689990289 942112073 913022831 873426572
output:
2077777981022497
result:
ok 1 number(s): "2077777981022497"
Test #7:
score: 0
Accepted
time: 27ms
memory: 5416kb
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: 3744kb
input:
3 438440875 694638152 602148637 704842539 545570589 318126837
output:
29598605011597
result:
ok 1 number(s): "29598605011597"
Test #9:
score: 0
Accepted
time: 19ms
memory: 5508kb
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: 1ms
memory: 3572kb
input:
3 890601211 849762562 605999387 661255602 303657951 233821688
output:
73864089514081
result:
ok 1 number(s): "73864089514081"
Test #11:
score: 0
Accepted
time: 27ms
memory: 5412kb
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: 3516kb
input:
3 532479135 802312680 383026733 250611794 10581891 880589538
output:
996357323326
result:
ok 1 number(s): "996357323326"
Test #13:
score: 0
Accepted
time: 27ms
memory: 5468kb
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: 1ms
memory: 3532kb
input:
3 334342343 342772366 896665872 14576399 379427577 632722734
output:
41053243453
result:
ok 1 number(s): "41053243453"
Test #15:
score: 0
Accepted
time: 26ms
memory: 5464kb
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: 3600kb
input:
3 998821231 676932324 272357182 590769365 946624815 705937945
output:
2479641613
result:
ok 1 number(s): "2479641613"
Test #17:
score: 0
Accepted
time: 19ms
memory: 5524kb
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: 3740kb
input:
3 29225426 356138255 284125635 389556472 707559815 841117504
output:
6220033
result:
ok 1 number(s): "6220033"
Test #19:
score: 0
Accepted
time: 28ms
memory: 5404kb
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: 1ms
memory: 3600kb
input:
3 690159823 248831820 196071252 836829317 630544210 921371411
output:
311361
result:
ok 1 number(s): "311361"
Test #21:
score: 0
Accepted
time: 25ms
memory: 5528kb
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: 1ms
memory: 3532kb
input:
3 40057493 123460374 850402613 568597464 872769893 571002924
output:
1974022
result:
ok 1 number(s): "1974022"
Test #23:
score: 0
Accepted
time: 24ms
memory: 5396kb
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: 1ms
memory: 3488kb
input:
3 463690546 747005237 787952632 658917860 938378614 909503798
output:
20733
result:
ok 1 number(s): "20733"
Test #25:
score: 0
Accepted
time: 23ms
memory: 5432kb
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: 3760kb
input:
3 632405220 747731085 687111312 938556941 119182922 700743523
output:
286
result:
ok 1 number(s): "286"
Test #27:
score: 0
Accepted
time: 1ms
memory: 3648kb
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: 3764kb
input:
3 975129587 963048662 708903358 391697135 686378450 606722801
output:
22
result:
ok 1 number(s): "22"
Test #29:
score: 0
Accepted
time: 0ms
memory: 3596kb
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: 1ms
memory: 3600kb
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"