QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#644519 | #6812. Draw a triangle | Ynoiynoi# | AC ✓ | 100ms | 3720kb | C++20 | 1.2kb | 2024-10-16 14:25:49 | 2024-10-16 14:25:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int exgcd(int a,int b,int &x,int &y) {
if(!b) {
x = 1; y = 0;
return a;
} else {
int d = exgcd(b,a%b,y,x); y -= x*(a/b);
return d;
}
}
signed main() {
int T;
cin >> T;
while(T --) {
int x1,y1,x2,y2;
cin >> x1 >> y1 >> x2 >> y2;
n = abs(x2-x1); m = abs(y2-y1);
int d = __gcd(n,m);
n /= d; m /= d;
bool r = 0;
int u,v;
int x,y;
if(n > 1 || m > 1) {
if(n < m) {
r = 1;
swap(n,m);
}
exgcd(n,m,u,v);
if(v < 0) v = v%n+n;
x = v;y = m*v/n;
if(r) swap(x,y);
// x *= d; y *= d;
// cout<<x<<" "<<y<<" "<<d<<"\n";
}
if(n == 1 && m == 1) {
x = 1; y = 0;
}
if(n == 1 && m == 0) {
x = 0; y = 1;
}
if(n == 0 && m == 1) {
x = 1; y = 0;
}
if(x1 > x2) x = -x;
if(y1 > y2) y = -y;
cout<<x1+x<<" "<<y1+y<<"\n";
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3600kb
input:
3 1 0 1 4 0 1 0 9 0 0 2 2
output:
2 0 1 1 1 0
result:
ok T=3 (3 test cases)
Test #2:
score: 0
Accepted
time: 80ms
memory: 3636kb
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:
66620472 -33485015 43307637 98028995 -88895354 -3180905 -90319828 20018513 -56783319 84789625 -81798087 90629099 98942862 -939227 -42532258 -57203579 53500176 -30665635 27114943 46989027 -2657436 26865440 40614023 17923268 -47650008 96037612 92954122 -64535082 86508758 -51415267 -82017733 17392543 7...
result:
ok T=50000 (50000 test cases)
Test #3:
score: 0
Accepted
time: 68ms
memory: 3636kb
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:
57869122 -31462318 -22048652 -27017568 80245592 -10283156 -96265093 -90677510 22392611 4659306 -85852434 89101437 -59733481 34194129 -64971150 90615333 52018810 -19951840 51552742 -19786133 -23565169 -10551161 -25830023 37587759 -8799496 83624956 9753822 -53464692 30266626 -36069373 -59557784 384873...
result:
ok T=50000 (50000 test cases)
Test #4:
score: 0
Accepted
time: 63ms
memory: 3720kb
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 -62927673 38837453 51846131 81700779 -17769085 -2355838 -67457905 38958895 -79916009 -22432181 -56740631 -30176822 95059849 -42037323 55544915 -42817852 -74016113 41116087 -55537083 74807768 67612816 -22054570 93125632 -1291962 -7415486 90952809 97296383 -29863898 79534330 9616866 -75170370...
result:
ok T=50000 (50000 test cases)
Test #5:
score: 0
Accepted
time: 85ms
memory: 3628kb
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:
47565991 63314608 -6671691 -8431435 -56437297 67409712 -19754618 97449355 22709359 -65094557 -9253460 92786300 60264823 -99332486 42759772 13104444 -59911937 -29129533 77502713 67904185 -25769424 -16449680 61092659 -55411800 -53400125 -61158222 -25069302 88946369 -21853227 -11367376 -27295568 -65634...
result:
ok T=50000 (50000 test cases)
Test #6:
score: 0
Accepted
time: 72ms
memory: 3620kb
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:
86077181 -33791183 70274129 92949013 -98644759 -36717070 -58640968 -37021163 47389291 88658577 41133806 -18298172 16742697 91602298 64705056 76220742 11696244 -41244758 -85775742 -61100847 67944226 10706490 86636084 -72743080 -80900519 -4929126 -15258421 -90513187 -57595914 -13548448 34137622 875626...
result:
ok T=49999 (49999 test cases)
Test #7:
score: 0
Accepted
time: 79ms
memory: 3620kb
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 -551175648 518914436 -177742226 -384034911 -588484916 -390232390 667134925 390686064 -493232151 -580589514 -326608659 -420275396 895639177 -50713300 835471744 260950327 -510154799 533361187 151183776 -349152331 -197515884 -162638542 122074436 -87976819 49989...
result:
ok T=50000 (50000 test cases)
Test #8:
score: 0
Accepted
time: 84ms
memory: 3580kb
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:
-513265195 -386177841 -595110719 -294135927 474757067 187395277 -204381765 -92881802 -90966308 191938251 439772547 -120648190 122561969 -101489867 362909276 -309396271 -458908877 449350296 101985857 -288291927 795202238 390932503 -622647959 -472251824 656284818 -342057776 -941951771 887636989 591948...
result:
ok T=50000 (50000 test cases)
Test #9:
score: 0
Accepted
time: 88ms
memory: 3656kb
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 373105214 567834009 -47815735 -227689628 160750960 -351224943 759255423 714643705 -390558911 -608284842 -334955170 453245240 180176629 122049014 257472404 758802235 722567929 185345979 -430083190 332112079 -277819252 147249181 811818734 510750874 -805751988 117991138 -468827463 -...
result:
ok T=50000 (50000 test cases)
Test #10:
score: 0
Accepted
time: 84ms
memory: 3636kb
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:
175907647 -476327168 255934168 302190473 875895611 -470291380 -165227375 -376974225 -534495777 597923610 -344797584 545756552 670131061 763122210 -172382142 -780520239 -112006078 -310805642 -99461229 694296700 311200059 406082577 507194200 -178696250 782929007 229259539 -300136497 371073894 -3809374...
result:
ok T=50000 (50000 test cases)
Test #11:
score: 0
Accepted
time: 84ms
memory: 3636kb
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:
32718222 3496373 -389429069 -60698343 -340089082 475009635 596447003 541841004 -59721163 -50924768 -487823724 171768342 603520353 -496202171 225597250 638958134 712087259 701845650 -681674591 944463724 247417889 106903882 -556373406 -374449096 329104402 391854098 287916358 504431314 441601157 -88526...
result:
ok T=50000 (50000 test cases)
Test #12:
score: 0
Accepted
time: 96ms
memory: 3636kb
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 -165831084 738903748 -246225164 -201016765 932450254 801556385 -28528191 475136627 321295795 259490125 34064370 -761776103 -195782177 -33056908 700996915 345053545 375833638 -497512580 -349004180 202285536 -397404377 -927740807 -820412666 469700568 -25069657 -652082394 -74925058...
result:
ok T=50000 (50000 test cases)
Test #13:
score: 0
Accepted
time: 88ms
memory: 3604kb
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:
170258232 401923601 440033434 -967952065 548615142 298444429 401290321 957292396 -6126948 143496384 120504822 -766628646 123466535 257181887 -700454338 389811435 -135764425 291300188 225399071 -689437667 181478635 -629865714 745707359 -316390926 -313282311 -504531801 -381891470 715514316 655993575 4...
result:
ok T=50000 (50000 test cases)
Test #14:
score: 0
Accepted
time: 54ms
memory: 3704kb
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:
-573784550 -2456461 -210461353 -397164860 570785181 -661843484 -9270099 -53602833 680980255 -156230289 395071181 679317778 439368857 235614788 -165189780 904520104 48638543 -452639985 -42650392 -819606648 -116369714 391977619 -853534856 -639377749 188506504 -801148575 -468264999 -399299 104523435 14...
result:
ok T=50000 (50000 test cases)
Test #15:
score: 0
Accepted
time: 100ms
memory: 3576kb
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:
615811205 -560998668 476677634 -513608149 343465219 11710533 55164368 -374551619 -394817988 -239225885 -797629850 165413014 720695658 -344686926 920807028 2896072 -524186170 610595075 698968311 720777834 -28604299 -665762004 -175178321 -579921966 -585521082 -707478112 545516141 -446733236 429779026 ...
result:
ok T=50000 (50000 test cases)
Test #16:
score: 0
Accepted
time: 84ms
memory: 3636kb
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:
-134831593 -662529172 286211073 -852892387 -566428685 541448418 -34807519 -304331182 39777135 -172079017 339388877 47425290 -55812108 -783803510 25503449 -386709974 500052696 113681508 940689483 -95344844 166080273 12678217 382354957 99847938 -684499497 -763114019 725695945 231652421 -25441007 59059...
result:
ok T=50000 (50000 test cases)
Test #17:
score: 0
Accepted
time: 95ms
memory: 3568kb
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:
-233826641 355141038 -178960176 447710754 152007220 -178331385 -702689557 -31590759 436084361 752849374 -445801934 372961127 -389798626 661751284 71809512 348876159 -805398146 249945576 235980749 -417818925 -438801981 -754840334 -410687822 -362443345 353137138 -23187480 361737954 -369236565 72098126...
result:
ok T=50000 (50000 test cases)
Test #18:
score: 0
Accepted
time: 91ms
memory: 3632kb
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:
-295461280 -450781744 -681202983 236774721 -609838587 775910988 -123156079 -332103415 -308648488 -281288696 -230813939 -570206020 -80882026 -425889995 599325617 104341415 173468219 -155052781 -301367720 -579396028 121558901 -162192911 -786938625 -100068032 -100636100 856996051 -366903790 516206772 -...
result:
ok T=50000 (50000 test cases)
Test #19:
score: 0
Accepted
time: 96ms
memory: 3636kb
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 -4788996 476368447 619740636 272650248 -262353729 -677439048 -369465323 167391411 148661394 -243966047 -49694672 -333729644 -890315881 -708373917 154903592 -116092068 -111273100 54019454 651973143 925118567 -296788040 -773429408 105348...
result:
ok T=50000 (50000 test cases)
Test #20:
score: 0
Accepted
time: 61ms
memory: 3580kb
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:
357605996 631866624 447870837 248729959 199651036 293175015 771157353 250369190 -319465377 574156487 722151227 -580513051 -405628990 61852489 329869663 924910034 744906586 -658899292 -532398178 424691878 -433945880 486168860 -739378607 -176021572 -728169864 250339196 163974604 204414487 271013711 -4...
result:
ok T=50000 (50000 test cases)
Test #21:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
3 -1000000000 -1000000000 1000000000 1000000000 -1000000000 -1000000000 1000000000 -1000000000 -1000000000 -1000000000 -1000000000 1000000000
output:
-999999999 -1000000000 -1000000000 -999999999 -999999999 -1000000000
result:
ok T=3 (3 test cases)