QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#768609 | #9168. Square Locator | ucup-team4352# | WA | 0ms | 3636kb | C++23 | 2.1kb | 2024-11-21 12:52:59 | 2024-11-21 12:53:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using LL = __int128;
ll ao2,bo2,co2,do2;
LL AO2,BO2,CO2,DO2;
LL AO=-1;
LL D=-1;
inline LL q2(LL x) {
return x*x;
}
inline LL calc(LL x) {
LL ans=2*x*x - 2*(bo2+do2)*x + q2(co2-bo2)+q2(co2-do2);
return ans;
}
struct Point {
LL x,y;
};
inline LL getDistance(Point p,Point q) {
return q2(p.x-q.x)+q2(p.y-q.y);
}
vector<Point> getPoint(LL Onow,LL D) {
LL OK = AO2+Onow-D;
// cout<<(ll)OK<<endl;
OK/=2*AO;
// cout<<(ll)OK<<endl;
vector<Point> a;
LL AK=AO-OK;
LL BK2=D-AK*AK;
LL BK=-1;
LL tmp=sqrtl(BK2);
// cout<<(ll)BK2<<endl;
for(LL i=max((LL)0,tmp-100);i<=tmp+100;i++) {
if(i*i==BK2) {
BK=i;
break;
}
}
// cout<<(ll)BK<<endl;
const LL pre[]={-1,1};
for(int i=0;i<2;i++) {
for(int j=0;j<2;j++) {
Point p={pre[i]*BK,pre[j]*OK};
if(getDistance(p,{0,0})==Onow)
a.push_back(p);
}
}
return a;
}
int check(Point a,Point b,Point c,Point d) {
if(getDistance(a,b)!=D || getDistance(b,c)!=D || getDistance(c,d)!=D || getDistance(d,a)!=D) return 0;
return 1;
}
void solve() {
cin>>ao2>>bo2>>co2>>do2;
AO2=ao2,BO2=bo2,CO2=co2,DO2=do2;
LL a=2,b=-2*(bo2+do2),c=q2(co2-bo2) + q2(co2-do2);
LL tmp = ( -b + sqrtl(b*b-4*a*c) )/(2*a);
for(LL i=max((LL)0,tmp-100000);i<=tmp+100000;i++) {
if(calc(i)==0) {
D=i;
break;
}
}
tmp=sqrtl(AO2);
for(LL i=max((LL)0,tmp-100);i<=tmp+100;i++) {
if(i*i==AO2) {
AO=i;
break;
}
}
auto Bp=getPoint(BO2,D);
auto Cp=getPoint(CO2,2*D);
auto Dp=getPoint(DO2,D);
// for(auto u:Bp) cout<<(ll)u.x<<" "<<(ll)u.y<<"\n";cout<<"\n";
// for(auto u:Cp) cout<<(ll)u.x<<" "<<(ll)u.y<<"\n";cout<<"\n";
// for(auto u:Dp) cout<<(ll)u.x<<" "<<(ll)u.y<<"\n";cout<<"\n";
for(auto b:Bp) {
for(auto c:Cp) {
for(auto d:Dp) {
if(check({0,AO},b,c,d)) {
cout<<(ll)AO<<" "<<(ll)b.x<<" "<<(ll)b.y<<" "<<(ll)c.x<<" "<<(ll)c.y<<" "<<(ll)d.x<<" "<<(ll)d.y;
return;
}
}
}
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3620kb
input:
36 5 10 41
output:
6 -1 2 3 1 4 5
result:
ok Answer is correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
1 1 1 1
output:
1 0 1 0 1 0 1
result:
ok Answer is correct
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3636kb
input:
1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000
output:
1000000000 -1000000000 0 0 1000000000 -1000000000 0
result:
wrong answer Not a square