QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#596523 | #9168. Square Locator | Hans# | TL | 0ms | 3956kb | C++23 | 2.9kb | 2024-09-28 15:57:34 | 2024-09-28 15:57:34 |
Judging History
answer
#include <cmath>
#include <iostream>
using namespace std;
struct coord {
long long int x;
long long int y;
};
#define _d(x, y) (pow((x), 2) + pow((y), 2))
struct coord a;
long long int da, db, dc, dd;
long long int bs, bl;
void find(long long int d, long long int low, long long int high) {
// Binary search high
long long int h = high, l = low;
long long int mh = high;
long long int sumD = _d(mh, l);
long long int sumN = _d(mh+1, l);
while (!(sumD <= d && sumN > d)) {
if (sumD <= d) {
l = mh;
} else {
h = mh;
}
mh = (l + h + 1)/2;
sumD = _d(mh, low);
sumN = _d(mh+1, low);
}
if (_d(low, mh) == d) {
bs = low;
bl = mh;
return;
}
// printf("mh is: %d\n", mh);
// Binary search low
h = mh, l = low;
long long int ml = low;
sumD = _d(ml, mh);
sumN = _d(ml-1, mh);
while (!(sumD >= d && sumN < d)) {
if (sumD < d) {
l = ml;
} else {
h = ml;
}
ml = (l+h+1)/2;
sumD = _d(mh, ml);
sumN = _d(mh, ml-1);
}
// printf("%d %d\n", ml, mh);
if (_d(ml, mh) == d) {
bs = ml;
bl = mh;
return;
}
find(d, ml, mh);
}
bool test(long long int x, long long int y) {
struct coord b, c, d;
b.x = a.x + x;
b.y = a.y + y;
c.x = b.x - y;
c.y = b.y + x;
d.x = c.x - x;
d.y = c.y - y;
// printf("%d %d, %d %d, %d %d\n", b.x, b.y, c.x, c.y, d.x, d.y);
long long int _db, _dc, _dd;
_db = pow(b.x,2) + pow(b.y, 2);
_dc = pow(c.x,2) + pow(c.y, 2);
_dd = pow(d.x,2) + pow(d.y, 2);
// printf("%d %d %d\n", _db, _dc, _dd);
if (
_db == db &&
_dc == dc &&
_dd == dd
) {
printf("%lld %lld %lld %lld %lld %lld %lld", a.y, b.x, b.y, c.x, c.y, d.x, d.y);
return true;
}
return false;
}
int main() {
cin >> da >> db >> dc >> dd;
a = {0ll, (int)sqrt(da)};
// while (true) {
// // long long int x, y;
// // cin >> x >> y;
// // test(a, x, y);
//
// // long long int x;
// // cin >> x;
// // find(x, 0, (int)sqrt(x) + 1);
// // printf("Ans: %d %d\n", sa, sb);
// }
find(db, 0, (long long int)sqrt(db)+1);
while (true) {
long long int rotX = bs - a.x;
long long int rotY = bl - a.y;
// cout << rotX << rotY;
#define check if (found) return 0;
bool found = false;
found = test(rotX, rotY); check
found = test(rotX, -rotY); check
found = test(-rotX, -rotY); check
found = test(-rotX, rotY); check
found = test(rotY, rotX); check
found = test(rotY, -rotX); check
found = test(-rotY, -rotX); check
found = test(-rotY, rotX); check
;
if (!found) {
bl--;
bs = sqrt(db - pow(bl, 2)) + 1;
if (bs > bl) {
return 0;
}
find(db, bs, bl-1);
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3908kb
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: 3804kb
input:
1 1 1 1
output:
1 0 1 0 1 0 1
result:
ok Answer is correct
Test #3:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000
output:
1000000000 0 1000000000 0 1000000000 0 1000000000
result:
ok Answer is correct
Test #4:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
4 10 8 2
output:
2 -1 3 -2 2 -1 1
result:
ok Answer is correct
Test #5:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
4 50 104 58
output:
2 5 5 2 10 -3 7
result:
ok Answer is correct
Test #6:
score: -100
Time Limit Exceeded
input:
9 16 65 58