QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#598343 | #9168. Square Locator | fosov | RE | 0ms | 3544kb | C++14 | 2.4kb | 2024-09-28 21:23:06 | 2024-09-28 21:23:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define INF 0x3f3f3f3f
#define LNF (ll) 0x3f3f3f3f3f3f3f3f
#define MOD 998244353
#define N 220
ll isqrt(ll x) {
ll l = 1, r = x;
while (l < r) {
ll m = l + (r - l) / 2;
if (m * m < x) {
l = m+1;
} else {
r = m;
}
}
return r;
}
int main() {
#ifdef TEST
freopen("zz.in", "r+", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll A, B, C, D; cin >> A >> B >> C >> D;
ll a = isqrt(A);
assert(((2ll * A + B - D) % (2ll * a)) == 0ll);
ll k = (2ll * A + B - D) / (2ll * a);
assert(4ll * k * k - 4ll * 2 * (k * k - B) > 0);
ll m = isqrt(4ll * k * k - 4ll * 2 * (k * k - B));
vector<tuple<ll, ll, ll, ll>> bd(4);
bd[0] = make_tuple((-2ll * k + m) / 4ll, 0, 0, 0);
bd[1] = make_tuple((-2ll * k - m) / 4ll, 0, 0, 0);
bd[2] = make_tuple((2ll * k + m) / 4ll, 0, 0, 0);
bd[3] = make_tuple((2ll * k - m) / 4ll, 0, 0, 0);
for (int i = 0; i < 2; ++ i) {
get<1>(bd[i]) = k + get<0>(bd[i]);
get<2>(bd[i]) = a - get<1>(bd[i]);
get<3>(bd[i]) = a + get<0>(bd[i]);
}
for (int i = 2; i < 4; ++ i) {
get<1>(bd[i]) = k - get<0>(bd[i]);
get<2>(bd[i]) = get<1>(bd[i]) - a;
get<3>(bd[i]) = a - get<0>(bd[i]);
}
ll ax = 0, ay = a;
for (int i = 0; i < 4; ++ i) {
auto [bx, by, dx, dy] = bd[i];
ll cx = dx - ax + bx;
ll cy = dy - ay + by;
if (cx * cx + cy * cy != C) continue;
cout << ay << ' ' << bx << ' ' << by << ' ';
cout << cx << ' ' << cy << ' ' << dx << ' ' << dy << '\n';
assert(ax * ax + ay * ay == A);
assert(bx * bx + by * by == B);
assert(cx * cx + cy * cy == C);
assert(dx * dx + dy * dy == D);
return 0;
}
return 0;
}
// A(0, a), B(x, y)
// AB = (x, y - a)
// v = (a - y, x) | (y - a, -x)
// D = (a - y, a + x) | (y - a, a - x)
// x^2 + y^2 = b^2
// 1:
// (a - y)^2 + (a + x)^2 = d^2
// 2a^2 - 2ay + 2ax + b^2 = d^2
// y-x = (2a^2 + b^2 - d^2) / 2a = k
// x^2 + (k+x)^2 = b^2
// 2x^2 + 2kx + k^2 - b^2 = 0;
// 2:
// (y - a)^2 + (a - x)^2 = d^2
// 2a^2 - 2ay - 2ax + b^2 = d^2
// x+y = k
// x^2 + (k-x)^2 = b^2;
// 2x^2 - 2kx + k^2 - b^2 = 0;
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3536kb
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: 3544kb
input:
1 1 1 1
output:
1 0 1 0 1 0 1
result:
ok Answer is correct
Test #3:
score: -100
Runtime Error
input:
1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000