QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#513226 | #9168. Square Locator | ucup-team3661# | RE | 0ms | 3576kb | C++20 | 2.7kb | 2024-08-10 17:14:58 | 2024-08-10 17:14:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
__int128_t mysqrt(__int128_t x) {
__int128_t ret = sqrt((long double)x);
while (ret * ret > x) ret--;
while ((ret + 1) * (ret + 1) <= x) ret++;
return ret;
}
int main() {
vector<ll> LEN(4);
for (int i = 0; i < 4; ++i) cin >> LEN[i];
vector<int> p(4);
iota(p.begin(), p.end(), 0);
ll ay = mysqrt(LEN[0]);
do {
if (p[0] != 0) break;
ll BD = LEN[p[3]] - LEN[p[1]];
if (BD % ay != 0) continue;
if ((BD / ay) % 2 != 0) continue;
__int128_t alpha = BD / ay / 2;
__int128_t CA = LEN[p[1]] - alpha * alpha - LEN[p[0]];
if (CA % 2 != 0) continue;
__int128_t beta = -CA / 2;
__int128_t H = alpha + ay;
H *= alpha + ay;
H += -beta * 4;
__int128_t leftL = mysqrt(H);
if (leftL * leftL != H) continue;
if ((leftL + alpha) % 2) continue;
{
ll ly = (leftL - alpha - ay) / 2;
ll lx = alpha + ly;
vector<ll> ansx(4), ansy(4);
ansx[p[0]] = 0;
ansx[p[1]] = ansx[p[0]] + lx;
ansx[p[2]] = ansx[p[0]] + lx - ly;
ansx[p[3]] = ansx[p[0]] - ly;
ansy[p[0]] = ay;
ansy[p[1]] = ansy[p[0]] + ly;
ansy[p[2]] = ansy[p[0]] + lx + ly;
ansy[p[3]] = ansy[p[0]] + lx;
bool flag = true;
for (int i = 0; i < 4; ++i) {
flag &= (ansx[i] * ansx[i] + ansy[i] * ansy[i]) == LEN[i];
}
if (true) {
cout << ansy[0] << ' ' << ansx[1] << ' ' << ansy[1] << ' ' << ansx[2] << ' ' << ansy[2] << ' ' << ansx[3] << ' ' << ansy[3] << endl;
return 0;
}
}
{
ll ly = (-leftL - alpha - ay) / 2;
ll lx = alpha + ly;
vector<ll> ansx(4), ansy(4);
ansx[p[0]] = 0;
ansx[p[1]] = ansx[p[0]] + lx;
ansx[p[2]] = ansx[p[0]] + lx - ly;
ansx[p[3]] = ansx[p[0]] - ly;
ansy[p[0]] = ay;
ansy[p[1]] = ansy[p[0]] + ly;
ansy[p[2]] = ansy[p[0]] + lx + ly;
ansy[p[3]] = ansy[p[0]] + lx;
bool flag = true;
for (int i = 0; i < 4; ++i) {
flag &= (ansx[i] * ansx[i] + ansy[i] * ansy[i]) == LEN[i];
}
if (true) {
cout << ansy[0] << ' ' << ansx[1] << ' ' << ansy[1] << ' ' << ansx[2] << ' ' << ansy[2] << ' ' << ansx[3] << ' ' << ansy[3] << endl;
return 0;
}
}
} while (next_permutation(p.begin(), p.end()));
assert(false);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3576kb
input:
36 5 10 41
output:
6 -1 2 3 1 4 5
result:
ok Answer is correct
Test #2:
score: -100
Runtime Error
input:
1 1 1 1