QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#235155 | #6812. Draw a triangle | zyfy# | AC ✓ | 49ms | 3564kb | C++14 | 1.4kb | 2023-11-02 15:20:47 | 2023-11-02 15:20:47 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
int extend_gcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int d = extend_gcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
void solve() {
int xx1, yy1, xx2, yy2;
cin >> xx1 >> yy1 >> xx2 >> yy2;
if (xx1 == xx2) {
cout << xx1 + 1 << " " << yy1 << endl;
} else if (yy1 == yy2) {
cout << xx1 << " " << yy1 + 1 << endl;
} else {
xx2 -= xx1;
yy2 -= yy1;
if (abs(xx2) == abs(yy2)) {
cout << xx2 + xx1 + 1 << " " << yy2 + yy1 << endl;
return;
}
int t = gcd(abs(xx2), abs(yy2));
xx2 /= t;
yy2 /= t;
int x = 0, y = 0;
if (xx2 >= 0 && yy2 >= 0 || xx2 <= 0 && yy2 <= 0) {
xx2 = abs(xx2);
yy2 = abs(yy2);
extend_gcd(abs(yy2), abs(xx2), x, y);
if (y > 0) {
x = -x;
y = x * yy2 / xx2;
y++;
} else {
y = x * yy2 / xx2;
}
} else {
xx2 = abs(xx2);
yy2 = abs(yy2);
extend_gcd(abs(yy2), abs(xx2), x, y);
if (y > 0) {
x = -x;
y = x * yy2 / xx2;
y++;
} else {
y = x * yy2 / xx2;
}
x = -x;
}
x += xx1;
y += yy1;
cout << x << " " << y << endl;
}
return;
}
signed main() {
ios::sync_with_stdio(false);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
}
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3404kb
input:
3 1 0 1 4 0 1 0 9 0 0 2 2
output:
2 0 1 1 3 2
result:
ok T=3 (3 test cases)
Test #2:
score: 0
Accepted
time: 27ms
memory: 3368kb
input:
50000 66620473 -33485015 66620223 -33485265 43307886 98029243 43307636 98028994 -88895230 -3180782 -88895480 -3181030 -90319745 20018595 -90319995 20018348 -56783257 84789686 -56783507 84789440 -81798038 90629147 -81798288 90628902 98942945 -939146 98942695 -939390 -42532151 -57203475 -42532401 -572...
output:
66620224 -33485265 43307887 98029244 -88895229 -3180781 -90319662 20018677 -56783195 84789747 -81798037 90629148 98942987 -939105 -42532044 -57203371 53500238 -30665575 27115165 46989241 -2657411 26865464 40614273 17923507 -47649883 96037731 92954372 -64534845 86508883 -51415149 -82017683 17392590 7...
result:
ok T=50000 (50000 test cases)
Test #3:
score: 0
Accepted
time: 37ms
memory: 3556kb
input:
50000 57869123 -31462316 57868973 -31462566 -22048649 -27017563 -22048799 -27017812 80245618 -10283113 80245468 -10283361 -96265076 -90677482 -96265226 -90677729 22392625 4659329 22392475 4659083 -85852423 89101455 -85852573 89101210 -59733414 34194238 -59733564 34193994 -64971121 90615380 -64971271...
output:
57869124 -31462314 -22048646 -27017558 80245644 -10283070 -96265059 -90677454 22392636 4659347 -85852412 89101473 -59733406 34194251 -64971100 90615414 52018885 -19951719 51552892 -19785892 -23565164 -10551153 -25829873 37587998 -8799421 83625075 9753872 -53464613 30266701 -36069255 -59557770 384875...
result:
ok T=50000 (50000 test cases)
Test #4:
score: 0
Accepted
time: 30ms
memory: 3400kb
input:
50000 -4816480 -62927672 -4816530 -62927922 38837454 51846136 38837404 51845887 81700780 -17769080 81700730 -17769328 -2355821 -67457821 -2355871 -67458068 38958908 -79915945 38958858 -79916191 -22432180 -56740626 -22432230 -56740871 -30176805 95059932 -30176855 95059688 -42037280 55545124 -42037330...
output:
-4816480 -62927671 38837455 51846141 81700781 -17769075 -2355804 -67457737 38958920 -79915886 -22432179 -56740621 -30176797 95059971 -42037273 55545158 -42817827 -74015992 41116137 -55536842 74807770 67612826 -22054520 93125871 -1291937 -7415367 90952859 97296620 -29863873 79534448 9616876 -75170323...
result:
ok T=50000 (50000 test cases)
Test #5:
score: 0
Accepted
time: 43ms
memory: 3520kb
input:
50000 47565990 63314613 47566040 63314364 -6671692 -8431430 -6671642 -8431678 -56437314 67409796 -56437264 67409549 -19754631 97449419 -19754581 97449173 22709358 -65094552 22709408 -65094797 -9253477 92786383 -9253427 92786139 60264780 -99332277 60264830 -99332520 42759753 13104536 42759803 1310429...
output:
47565989 63314618 -6671693 -8431425 -56437331 67409880 -19754643 97449478 22709357 -65094547 -9253485 92786422 60264773 -99332243 42759747 13104565 -59911987 -29129292 77502711 67904195 -25769474 -16449441 61092634 -55411681 -53400175 -61157985 -25069327 88946487 -21853237 -11367329 -27295593 -65633...
result:
ok T=50000 (50000 test cases)
Test #6:
score: 0
Accepted
time: 34ms
memory: 3368kb
input:
49999 86077178 -33791178 86077328 -33791427 70274103 92949056 70274253 92948808 -98644776 -36717042 -98644626 -36717289 -58640982 -37021140 -58640832 -37021386 47389280 88658595 47389430 88658350 41133739 -18298063 41133889 -18298307 16742668 91602345 16742818 91602102 64705012 76220813 64705162 762...
output:
86077175 -33791173 70274077 92949099 -98644793 -36717014 -58640993 -37021122 47389269 88658613 41133731 -18298050 16742647 91602379 64704981 76220863 11696094 -41244517 -85775747 -61100839 67944076 10706729 86636009 -72742961 -80900569 -4929047 -15258496 -90513069 -57595928 -13548426 34137597 875626...
result:
ok T=49999 (49999 test cases)
Test #7:
score: 0
Accepted
time: 38ms
memory: 3368kb
input:
50000 -370035325 -480207325 197507381 563102266 -447653163 -13791299 712913474 279375990 -164085901 515918101 -746049282 520422889 -351774171 -526736185 986786085 570845376 -139080671 -314883129 -653624395 -401153986 371330972 295281720 716532063 406617905 713639850 932579042 -697994312 -837319029 -...
output:
-300769848 -352877107 -339517866 13524437 -358959535 517426554 -177742226 -384034911 -73941192 -303961533 420728110 311213561 918402011 1189308557 -385131636 -550186425 -768505152 512420405 839320794 405630469 -1224302229 1229827109 315035793 -386859054 -745518843 -228563363 -102621212 632478207 960...
result:
ok T=50000 (50000 test cases)
Test #8:
score: 0
Accepted
time: 31ms
memory: 3408kb
input:
50000 38026624 -878076357 -552920439 -350794846 -412973070 -567080550 -956686128 247707367 293749788 -47698118 949332510 803776854 -37716684 -75717498 -384102742 -111390691 252319124 -407086186 -298274705 553686185 195690205 -960978213 693203670 751867944 -44794927 146815392 497184663 -657312706 244...
output:
-1628620 -842693362 -595110719 -294135927 440533870 142945973 128948397 -58553194 45010727 -45338252 439772547 -120648190 -148427826 300574182 362909276 -309396271 85851387 95042407 774324098 282899618 811014396 392333049 -727650943 -623255007 327131395 134077126 -512989063 843903152 591948260 -2533...
result:
ok T=50000 (50000 test cases)
Test #9:
score: 0
Accepted
time: 44ms
memory: 3560kb
input:
50000 25273482 -271356160 203127555 -184489837 -289853919 200578127 408716355 587561320 440221844 -73945468 -375731352 -330991327 452223216 -181778460 -163936693 -539981093 538901710 569206009 766705704 719561034 -491626613 -671982599 527872032 -29445214 -63710429 421304993 -622588079 487115265 -476...
output:
48376926 -260072127 -254242778 220305438 768137461 29356231 743695472 -12331977 546351991 574123338 -390558911 -608284842 -71904513 422269882 -1132725863 1677750508 75179887 292207306 724253563 193054663 -427865588 355781439 -192970889 -184358428 859016516 522350820 -754163006 344585166 -468870824 -...
result:
ok T=50000 (50000 test cases)
Test #10:
score: 0
Accepted
time: 49ms
memory: 3560kb
input:
50000 -35259334 -701474112 311852823 -331381965 572375773 934385697 63613329 -82033074 963625204 106699315 855551972 -604089908 -239314379 -375979612 122091992 -380831468 -884798360 -827592392 -450362161 940295667 -209340085 -40153027 -361999245 620160834 877357984 882062152 315363830 559500049 -414...
output:
100685842 -556528909 764696612 1318609244 983968843 240497843 -313401383 -374984999 -800664744 -485220335 -226541746 34251255 1084584907 1001002094 -391318098 -916030160 -124253717 -315185824 327568478 -496145635 158607620 -106166975 -816191376 684210367 791144144 232228128 -654445293 478026628 -115...
result:
ok T=50000 (50000 test cases)
Test #11:
score: 0
Accepted
time: 46ms
memory: 3564kb
input:
50000 -3663853 -177781773 173552690 705221364 -960654525 -342974336 754897176 504780355 494495391 471831124 -843629424 476927366 348629524 -909106658 627892786 725953059 -523367521 102557145 502351897 -236989097 -299381834 260178935 -743399500 51860789 335298045 -183924414 720046790 -631868047 17038...
output:
19026253 -64725540 -960029414 -342665432 -9044951 473748855 380075307 -724994603 -572580872 118848353 -265814891 275927415 218771608 -48258538 115179588 639089048 839592383 785153980 -766615959 1011286582 -64561893 611929546 -506797283 -656030854 375273407 1026931962 627475205 1119539297 441601157 -...
result:
ok T=50000 (50000 test cases)
Test #12:
score: 0
Accepted
time: 39ms
memory: 3524kb
input:
50000 87994422 -469168315 -282663695 303996144 -153451281 -314512069 -168298547 948863838 -293926308 -170703744 789655924 -859296264 930120677 671761062 934908485 938519828 -62509863 497504980 258338790 286307134 166058928 434063507 329625200 250123198 170938223 -712363899 -476975593 -946264304 -351...
output:
-73237496 -132850876 -155918744 -104551979 -341627452 -140390723 930185004 675345122 -96491535 519873333 157729523 443430434 307812076 -662951695 -195782177 -33056908 1224580665 1310897491 589289787 -794758090 -493386639 147223359 -397404377 -927740807 -820412666 469700568 -25069657 -652082394 51548...
result:
ok T=50000 (50000 test cases)
Test #13:
score: 0
Accepted
time: 24ms
memory: 3372kb
input:
50000 75983688 322870644 646834996 801552184 519110129 -976686263 -819619684 -828820558 570394281 246976850 519558688 367109464 621047758 927882674 148954683 991061997 88827271 210457738 -857995083 -457237784 112341241 -890456500 223281366 792319429 -102888330 389111504 665082474 -58495814 -70874021...
output:
124421971 363488072 440033434 -967952065 548615142 298444429 401290321 957292396 183781490 277419092 120504822 -766628646 -260518867 480985546 -700454338 389811435 -135764425 291300188 12516190 -241893111 503406712 -698931583 885484900 -568892032 -889911523 432127416 -675551252 849503528 710071011 6...
result:
ok T=50000 (50000 test cases)
Test #14:
score: 0
Accepted
time: 26ms
memory: 3340kb
input:
50000 -805634427 81825426 509577423 -396279363 -267738158 -532191054 179134956 521282089 893958536 -637235181 -336434702 -730924494 209380302 -981860939 -104731724 351669816 693569118 -145872073 215960733 -538852028 278991643 856418697 472101398 561793859 773440456 -666647571 296326173 621945233 -88...
output:
-1012188500 156911802 -210461353 -397164860 1217131891 -612626878 113918677 -576588290 706157981 -135513857 201961426 973942616 630397772 -280317126 -884801087 -292336810 330976910 1073742605 -581047935 -674814364 -411742365 424356417 -602871602 -585984543 188506504 -801148575 -528265673 1577653794 ...
result:
ok T=50000 (50000 test cases)
Test #15:
score: 0
Accepted
time: 44ms
memory: 3404kb
input:
50000 725941728 -610067425 488068370 -504082729 476613211 -620476119 476920048 -111480150 245593358 -660602217 471175896 888995542 280795134 -289504448 -967836825 -760152213 -486471673 -224674228 934607251 -450295850 -694176146 751372343 -891227475 -364721717 830792306 -773436907 523127672 424703167...
output:
717135572 -606143834 476651067 -557678766 343465219 11710533 506425900 -204457277 -578125358 -210122571 -600578521 1281507074 787056637 -603116851 941771668 105087926 -406162203 976246623 712961166 700340428 1292595062 73581223 -175178321 -579921966 1014800099 736479508 545516141 -446733236 10693734...
result:
ok T=50000 (50000 test cases)
Test #16:
score: 0
Accepted
time: 43ms
memory: 3404kb
input:
50000 104556371 -685734071 -731906759 -604652123 396789892 -935692027 -576229790 -207110549 -578953998 541207525 -516985486 542399334 -878495739 -596088045 119106374 -251106029 -363926466 866046756 158763085 -478051966 599120280 -275757280 -282204734 820871313 -588932159 -793669810 680396515 -770178...
output:
-74287230 -668397996 286211073 -852892387 -566428685 541448418 -724581846 -542862892 -482912416 1172019705 339388877 47425290 -487387873 -791790559 25503449 -386709974 1028398495 304290062 1034491217 -55269710 -996151009 1216957576 -86988429 1590172268 -921828695 -702461193 26028538 1182106273 35761...
result:
ok T=50000 (50000 test cases)
Test #17:
score: 0
Accepted
time: 41ms
memory: 3560kb
input:
50000 -913971105 -802525545 -62443082 646851152 582546207 -691701688 -263954188 574883995 -88743623 992720648 272194515 -762942323 -840733072 -332078482 -575663610 244914353 440623464 752008161 -470122956 920792991 -757686511 643488102 708042881 -627877550 185019277 307661180 -692173668 848015507 75...
output:
-742587546 -510815431 497552195 -564528447 -208930918 1577331586 -713707125 -55573370 436084361 752849374 -812234282 690802540 -117355765 493925403 75795503 450177074 -1056252969 627582280 235980749 -417818925 -438801981 -754840334 -479814670 -261811507 -623307914 557149163 361737954 -369236565 7736...
result:
ok T=50000 (50000 test cases)
Test #18:
score: 0
Accepted
time: 47ms
memory: 3364kb
input:
50000 185492989 3104323 -418943377 -567314244 -716676172 339998445 -419312863 -525301490 -610060612 777476899 -418834808 -571211717 39944725 -455257290 -829398804 201165129 -466129455 -464184034 735772464 931681523 -466599024 -740319024 563884212 3148693 -505528308 -808674422 -6340257 -358696593 -85...
output:
308975086 119636823 -752149361 443222169 -610282637 779042810 -123156079 -332103415 -308648488 -281288696 -230813939 -570206020 -430986539 -741481020 -389455140 149375614 161096481 -135587065 272506246 -277045857 153342368 -193102195 -815413403 -128364793 -68157140 1036119609 154718475 -215574939 35...
result:
ok T=50000 (50000 test cases)
Test #19:
score: 0
Accepted
time: 45ms
memory: 3360kb
input:
50000 -474636599 -626920443 712875021 -348747799 -342048305 37518714 -249508888 482083100 -410519206 -225607946 27339059 407774804 -345676873 559668812 88853181 453485769 999517103 522173138 135806165 -45307125 -285232985 -711392209 656546715 686223071 -736883128 630709030 260930401 -627544060 34322...
output:
-336085368 -594465045 -307990953 201132083 -407219196 -220834325 -439319050 582551490 1379293570 771696028 -262353729 -677439048 -1104300933 1094026649 148661394 -243966047 -49694672 -333729644 -948747113 -638914191 152518387 -144927251 -845455967 657325213 778772578 942376469 -321051363 -781665466 ...
result:
ok T=50000 (50000 test cases)
Test #20:
score: 0
Accepted
time: 47ms
memory: 3516kb
input:
50000 626800159 776374206 -41956635 417375236 -536924579 414783144 847473468 181350188 103033152 456387414 906877647 -901512211 784792043 -200142589 761424984 571942095 -319313812 593906734 -329157602 -688825321 790537948 -567376329 -989657217 -909342264 82546755 272767210 -982948739 -187576605 3536...
output:
691984393 811366109 -936527210 482162915 38882137 564754940 775059674 121430316 -319286399 597478888 858924669 -554239607 570722500 483681931 377342987 1063174476 744906586 -658899292 -429161671 365066184 -394404104 788104158 -739378607 -176021572 -744833128 288254918 -158248530 290364360 212765163 ...
result:
ok T=50000 (50000 test cases)
Test #21:
score: 0
Accepted
time: 1ms
memory: 3396kb
input:
3 -1000000000 -1000000000 1000000000 1000000000 -1000000000 -1000000000 1000000000 -1000000000 -1000000000 -1000000000 -1000000000 1000000000
output:
1000000001 1000000000 -1000000000 -999999999 -999999999 -1000000000
result:
ok T=3 (3 test cases)