QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#305624 | #6812. Draw a triangle | lmeowdn# | AC ✓ | 23ms | 4056kb | C++14 | 2.0kb | 2024-01-15 18:37:00 | 2024-01-15 18:37:00 |
Judging History
answer
//vanitas vanitatum et omnia vanitas
#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
int ax,bx,ay,by,tss,ansx,ansy;
int sz(int x,int y) {
int sx=x-ax, sy=y-ay;
int tx=x-bx, ty=y-by;
int ss=sx*ty-sy*tx;
if(ss<0) ss=-ss;
return ss;
}
void exgcd(int a,int b,int &x,int &y) {
if(a<b) {exgcd(b,a,y,x); return;}
if(b==0||a==1) {x=1, y=0; return;}
int nx,ny; exgcd(b,a%b,nx,ny);
x=ny, y=nx-(a/b)*ny;
}
signed main() {
int T=read();
while(T--) {
ax=read(), ay=read(), bx=read(), by=read();
int dx=ax-bx, dy=by-ay;
int g=__gcd(dx,dy);
dx/=g, dy/=g; int x=0,y=0;
bool rx=0, ry=0;
if(dx<0) rx=1, dx=-dx; if(dy<0) ry=1, dy=-dy;
exgcd(dy,dx,x,y);
if(rx) x=-x; if(ry) y=-y;
printf("%lld %lld\n",ax+x,ay+y);
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3952kb
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: 10ms
memory: 3732kb
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 43307885 98029242 -88895231 -3180783 -90319828 20018513 -56783319 84789625 -81798039 90629146 98942903 -939187 -42532258 -57203579 53500176 -30665635 27114943 46989027 -2657413 26865462 40614091 17923333 -47649925 96037691 92954218 -64534991 86508847 -51415183 -82017717 17392558 7...
result:
ok T=50000 (50000 test cases)
Test #3:
score: 0
Accepted
time: 13ms
memory: 3776kb
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 22392614 4659311 -85852434 89101437 -59733422 34194225 -64971142 90615346 52018823 -19951819 51552770 -19786088 -23565168 -10551159 -25829991 37587810 -8799479 83624983 9753834 -53464673 30266687 -36069277 -59557784 384873...
result:
ok T=50000 (50000 test cases)
Test #4:
score: 0
Accepted
time: 9ms
memory: 3712kb
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 38958896 -79916004 -22432181 -56740631 -30176813 95059893 -42037287 55545090 -42817839 -74016050 41116115 -55536948 74807768 67612816 -22054538 93125785 -1291945 -7415405 90952813 97296402 -29863887 79534382 9616870 -75170351...
result:
ok T=50000 (50000 test cases)
Test #5:
score: 0
Accepted
time: 10ms
memory: 3736kb
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 -19754619 97449360 22709357 -65094547 -9253469 92786344 60264787 -99332311 42759759 13104507 -59911965 -29129398 77502711 67904195 -25769456 -16449527 61092642 -55411719 -53400129 -61158203 -25069313 88946421 -21853231 -11367357 -27295587 -65633...
result:
ok T=50000 (50000 test cases)
Test #6:
score: 0
Accepted
time: 13ms
memory: 3776kb
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 -58640971 -37021158 47389269 88658613 41133747 -18298076 16742689 91602311 64705043 76220763 11696216 -41244713 -85775743 -61100845 67944194 10706541 86636067 -72743053 -80900531 -4929107 -15258482 -90513091 -57595928 -13548426 34137615 875626...
result:
ok T=49999 (49999 test cases)
Test #7:
score: 0
Accepted
time: 18ms
memory: 3720kb
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:
-439300802 -607537543 -555788460 -41107035 -358959535 517426554 -525806116 -669437459 -204220150 -325804725 321933834 279349879 508877689 675849527 -594439442 -1014814061 -768505152 512420405 835471744 260950327 -510154799 533361187 315035793 -386859054 -1049140339 -265089065 -102621212 632478207 49...
result:
ok T=50000 (50000 test cases)
Test #8:
score: 0
Accepted
time: 22ms
memory: 3980kb
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 146965706 -238342209 -204381765 -92881802 459627521 -768834120 -48392137 -1801308236 58837972 -6943398 126987054 -638870451 85851387 95042407 426551310 -12554164 795202238 390932503 -728955709 -625131371 521312587 -146814508 -512989063 843903152 591948260 -2...
result:
ok T=50000 (50000 test cases)
Test #9:
score: 0
Accepted
time: 22ms
memory: 3772kb
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:
2170038 -282640193 -325465060 180850816 112306227 -177247167 160750960 -351224943 531451429 564288680 -592694315 -735680356 -71904513 422269882 -1132725863 1677750508 -70229101 -79980744 722567929 185345979 -430083190 332112079 -123300587 -456646560 811818734 510750874 -805751988 117991138 -48082427...
result:
ok T=50000 (50000 test cases)
Test #10:
score: 0
Accepted
time: 23ms
memory: 3772kb
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:
-171204510 -846419315 380054934 550162150 943281565 -27099213 -165227375 -376974225 -968931976 -1169964449 -192138424 -114557309 670131061 763122210 -437610224 -944682568 -331646277 -389356622 453213420 -846409459 -150043914 -1142303569 -816191376 684210367 783974970 229637504 -300136497 371073894 -...
result:
ok T=50000 (50000 test cases)
Test #11:
score: 0
Accepted
time: 23ms
memory: 4056kb
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:
-26353959 -290838006 -961279636 -343283240 -9044951 473748855 317183741 -1093218713 -572580872 118848353 -332948777 244430455 451824482 -319590290 225597250 638958134 712087259 701845650 -681674591 944463724 -64561893 611929546 -421472861 -1140655292 359647619 811991396 386107475 682303693 441601157...
result:
ok T=50000 (50000 test cases)
Test #12:
score: 0
Accepted
time: 21ms
memory: 3788kb
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 -150983818 -524472159 -246225164 -201016765 930056350 668177002 -28528191 475136627 174388333 424696580 34064370 -761776103 -506516031 -473600446 700996915 345053545 621618259 -839776672 -672184763 79036309 -397404377 -927740807 -848840306 467007182 -193051635 -711178438 3533103...
result:
ok T=50000 (50000 test cases)
Test #13:
score: 0
Accepted
time: 22ms
memory: 3720kb
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:
27545405 282253216 598186824 -985420461 548615142 298444429 840805195 898472952 -6126948 143496384 104177660 -1014284354 -260518867 480985546 -717026094 373004537 -108953827 266708170 191111104 -617353933 503406712 -698931583 1062815658 -889231138 -378779081 -398140810 -381891470 715514316 655993575...
result:
ok T=50000 (50000 test cases)
Test #14:
score: 0
Accepted
time: 23ms
memory: 3772kb
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 -325014963 -667217248 570785181 -661843484 304841927 -1387133588 680980255 -156230289 356021860 738894778 916483140 -1052978016 -889944441 -300891232 201999286 376461531 -581047935 -674814364 -411742365 424356417 -853534856 -639377749 672768568 -908357705 -479512623 295419842 1...
result:
ok T=50000 (50000 test cases)
Test #15:
score: 0
Accepted
time: 19ms
memory: 3728kb
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 476575355 -683273472 147721497 -1332914967 55164368 -374551619 -394817988 -239225885 -787773771 221237612 874527975 -943756963 920807028 2896072 -419727851 934218717 718235878 692636394 569646712 -330980709 -578034479 -670886758 769087595 514774986 533232107 -492981646 429779026...
result:
ok T=50000 (50000 test cases)
Test #16:
score: 0
Accepted
time: 22ms
memory: 3788kb
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 507368711 -1018491667 -591479311 540966632 -1032409632 -649313198 -244940516 560073807 339388877 47425290 -690476445 -795549061 -16524549 -400148866 609533229 153178228 940689483 -95344844 -8085631 193145226 -86988429 1590172268 -684499497 -763114019 536075966 489239151 35761878...
result:
ok T=50000 (50000 test cases)
Test #17:
score: 0
Accepted
time: 22ms
memory: 3984kb
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:
-1085354664 -1094235659 667540219 -818874929 31443672 408109710 -967759019 -608583594 445162567 751166948 -812234282 690802540 -117355765 493925403 74747747 423549156 -814436809 263552374 894392963 -709311001 -544283249 -933197048 -479814670 -261811507 -623307914 557149163 -2483270 -573052515 731580...
result:
ok T=50000 (50000 test cases)
Test #18:
score: 0
Accepted
time: 22ms
memory: 3724kb
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:
62010892 -113428177 -752149361 443222169 -610282637 779042810 203045529 -578411165 -623610422 -647079372 -702384109 -910432028 -580070077 -875867824 -389455140 149375614 161096481 -135587065 238849896 -294777979 153342368 -193102195 -815707401 -128656953 -100636100 856996051 226664597 -316507855 350...
result:
ok T=50000 (50000 test cases)
Test #19:
score: 0
Accepted
time: 19ms
memory: 3716kb
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:
-613187830 -659375841 -376105657 -126094655 -413819216 -230381567 -439319050 582551490 619740636 272650248 -308112241 -745345370 -1104300933 1094026649 537780986 -573476217 -615246506 -538603546 -948747113 -638914191 67182423 -1176569453 -845455967 657325213 749276164 938361891 -684453655 -905020472...
result:
ok T=50000 (50000 test cases)
Test #20:
score: 0
Accepted
time: 23ms
memory: 3672kb
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:
561615925 741382303 -936527210 482162915 167184167 348019888 794524412 -521715494 -319341225 590334580 722151227 -580513051 -405628990 61852489 329869663 924910034 744906586 -658899292 -429161671 365066184 -433945880 486168860 -752005041 -178093816 -744833128 288254918 -158248530 290364360 250985977...
result:
ok T=50000 (50000 test cases)
Test #21:
score: 0
Accepted
time: 0ms
memory: 3732kb
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)