QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#598343#9168. Square LocatorfosovRE 0ms3544kbC++142.4kb2024-09-28 21:23:062024-09-28 21:23:07

Judging History

你现在查看的是最新测评结果

  • [2024-09-28 21:23:07]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3544kb
  • [2024-09-28 21:23:06]
  • 提交

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

output:


result: