QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#589411 | #6812. Draw a triangle | Sunlight9# | WA | 31ms | 3660kb | C++20 | 1.5kb | 2024-09-25 17:45:47 | 2024-09-25 17:45:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll =__int128;
//using ll = long long;
int t;
ll x,y,a,b,c;
void ex_gcd(long long int al,long long int bl)
{
if(bl==0LL)
{
x=1LL;y=0LL;return;
}
else
{
ex_gcd(bl,al%bl);
long long tmp=x;
x=y;y=tmp-y*(al/bl);
}
}
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
long long x1,x2,y1,y2,x3,y3;
cin>>t;
while(t--)
{
cin>>x1>>y1>>x2>>y2;
if(x1==x2)
{
cout<<x1+1LL<<" 1\n";
continue;
}
if(y1==y2)
{
cout<<"1 "<<y1+1LL<<'\n';
continue;
}
a=y1-y2;b=x2-x1;
c=x2*y1-x1*y2;
ll aa=a,bb=b;
if(aa<0) aa=-aa;
if(bb<0) bb=-bb;
ll gcdk=__gcd(aa,bb);
// a/=gcdk;b/=gcdk;
ll num_l=c/gcdk;
if(c%gcdk==0LL) num_l--;
ll num_r=c/gcdk;
if(c%gcdk==0LL) num_r++;
ll sum1=c-num_l*gcdk;
ll sum2=num_r*gcdk-c;
ll num;
if(sum1<=sum2) num=num_l;
else num=num_r;
// cerr<<a<<" "<<b<<" "<<c<<" asd"<<endl;
ex_gcd(a,b);
// cerr<<x<<" "<<y<<" "<<c<<" asd"<<endl;
x*=num;y*=num;
// if(x>1e18)
// {
//
// }
assert(x <= 1E18 and y <= 1E18);
assert(x >= -1E18 and y >= -1E18);
cout<<format("{}", x) <<" "<< format("{}", y) <<'\n';
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3648kb
input:
3 1 0 1 4 0 1 0 9 0 0 2 2
output:
2 1 1 1 0 -1
result:
ok T=3 (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 31ms
memory: 3660kb
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:
0 100105487 -13723647137 -13723647137 -10625410771 -10625410771 -2267030938578 -2239717312812 -1090149184444 -1072566133082 -8539561213 -8539561213 511914166638 499725734099 424314497992 412417829824 319508495801 309201770130 -578593659057 -557743437109 -735414464 -735414464 475560039227 45465630123...
result:
wrong answer wa on query #1 (test case 1)