QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#519189#9168. Square Locatorucup-team1329AC ✓1ms3868kbC++142.3kb2024-08-14 17:10:572024-08-14 17:10:57

Judging History

This is the latest submission verdict.

  • [2024-08-14 17:10:57]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 3868kb
  • [2024-08-14 17:10:57]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-10;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
// int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
// int dir[8][2] = {{1, 0}, {1, -1}, {1, 1}, {0, 1}, {0, -1}, {-1, 1}, {-1, 0}, {-1, -1}};
const int INF = 0x3f3f3f3f;
const double Pi = acos(-1);
__int128 sq(__int128 x) {
    __int128 l = 0, r = 4e18 + 10;
    while (r > 1 + l) {
        __int128 mid = l + r >> 1;
        if (mid * mid <= x)
            l = mid;
        else
            r = mid;
    }
    return l;
}

struct point {
    __int128 x, y;
    point clk90(point B) {
        __int128 dx = B.x - x;
        __int128 dy = B.y - y;
        return {x + dy, y - dx};
    }
    point anti_clk90(point B) {
        __int128 dx = B.x - x;
        __int128 dy = B.y - y;
        return {x - dy, y + dx};
    }
};
__int128 len2(point B) {
    return B.x * B.x + B.y * B.y;
}
point A, B, C, D;
__int128 d1, d2, d3, d4;
void check(__int128 temp) {
    B.y = (d1 + d2 - temp) / 2 / A.y;
    B.x = sq(d2 - B.y * B.y);
    C = B.clk90(A);
    D = C.clk90(B);
    if (len2(C) == d3 && len2(D) == d4) {
        cout << (ll)A.y << ' ' << (ll)B.x << ' ' << (ll)B.y << ' ';
        cout << (ll)C.x << ' ' << (ll)C.y << ' ' << (ll)D.x << ' ' << (ll)D.y;
        exit(0);
    }
    B.x = -B.x;
    C = B.clk90(A);
    D = C.clk90(B);
    if (len2(C) == d3 && len2(D) == d4) {
        cout << (ll)A.y << ' ' << (ll)B.x << ' ' << (ll)B.y << ' ';
        cout << (ll)C.x << ' ' << (ll)C.y << ' ' << (ll)D.x << ' ' << (ll)D.y;
        exit(0);
    }
}

void solve() {
    ll aa, bb, cc, dd;
    cin >> aa >> bb >> cc >> dd;
    d1 = aa, d2 = bb, d3 = cc, d4 = dd;
    A = {0, sq(aa)};
    __int128 a = 2;
    __int128 b = -2 * (d2 + d4);
    __int128 c = (2 * d1 * d1 + d2 * d2 + d4 * d4 - 2 * d1 * d2 - 2 * d1 * d4);
    __int128 temp = sq(b * b - 4 * a * c);
    __int128 x1 = (temp - b) / 2 / a;
    __int128 x2 = (-1 * temp - b) / 2 / a;
    check(x1);
    check(x2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3608kb

input:

36 5 10 41

output:

6 -2 1 3 -1 5 4

result:

ok Answer is correct

Test #2:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

1 1 1 1

output:

1 -1 0 0 -1 1 0

result:

ok Answer is correct

Test #3:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000

output:

1000000000 -1000000000 0 0 -1000000000 1000000000 0

result:

ok Answer is correct

Test #4:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

4 10 8 2

output:

2 -3 1 -2 -2 1 -1

result:

ok Answer is correct

Test #5:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

4 50 104 58

output:

2 -5 -5 2 -10 7 -3

result:

ok Answer is correct

Test #6:

score: 0
Accepted
time: 0ms
memory: 3836kb

input:

9 16 65 58

output:

3 0 -4 7 -4 7 3

result:

ok Answer is correct

Test #7:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

25 13 101 113

output:

5 2 -3 10 -1 8 7

result:

ok Answer is correct

Test #8:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

16 25 58 49

output:

4 -4 -3 3 -7 7 0

result:

ok Answer is correct

Test #9:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

374544 2235250 4453364 2592658

output:

612 -1205 -885 292 -2090 1497 -593

result:

ok Answer is correct

Test #10:

score: 0
Accepted
time: 0ms
memory: 3524kb

input:

126736 551200 1838608 1414144

output:

356 124 -732 1212 -608 1088 480

result:

ok Answer is correct

Test #11:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

6007401 6936277 5051405 4122529

output:

2451 -2599 426 -574 -2173 2025 -148

result:

ok Answer is correct

Test #12:

score: 0
Accepted
time: 0ms
memory: 3524kb

input:

2209 2536706 4875777 2341280

output:

47 -1435 691 -2079 -744 -644 -1388

result:

ok Answer is correct

Test #13:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

986962771600 2474826790757 5529645464114 4041781444957

output:

993460 -1210079 -1005254 788635 -2215333 1998714 -216619

result:

ok Answer is correct

Test #14:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

722790729241 782340801290 3904082690373 3844532618324

output:

850171 68947 -881809 1800927 -812862 1731980 919118

result:

ok Answer is correct

Test #15:

score: 0
Accepted
time: 0ms
memory: 3528kb

input:

3870332944 287487526720 654504136912 370886943136

output:

62212 77528 -530544 670284 -453016 592756 139740

result:

ok Answer is correct

Test #16:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

42230661001 2038831296200 3308981375377 1312380740178

output:

205501 -1201498 771514 -1767511 -429984 -566013 -995997

result:

ok Answer is correct

Test #17:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

132551656347532249 102473514386838101 439829344402853445 469907486363547593

output:

364076443 -144905351 -285439930 504611022 -430345281 649516373 219171092

result:

ok Answer is correct

Test #18:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

55636209407170681 109515374676898429 329424831462677605 275545666192949857

output:

235873291 -168654810 -284729573 351948054 -453384383 520602864 67218481

result:

ok Answer is correct

Test #19:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

466589422796014144 325095618166198298 43553814262839476 185047618892655322

output:

683073512 -483684563 301902073 -102513124 -181782490 381171439 199388949

result:

ok Answer is correct

Test #20:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

6909562468993284 229067899424048957 357610810027741258 135452473072685585

output:

83123778 -423763499 222468866 -563108587 -201294633 -139345088 -340639721

result:

ok Answer is correct

Test #21:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

5000019216542596 408275955794662066 885792080806957480 482516144228838010

output:

70710814 -163457821 -617703405 524956398 -781161226 688414219 -92747007

result:

ok Answer is correct

Test #22:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

1736111972222329 40264917317940640 105455671025820505 66926865680102194

output:

41666677 111335636 -166940988 319943301 -55605352 208607665 153002313

result:

ok Answer is correct

Test #23:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

255964325056888900 56517928013623933 645740568455742866 845186965499007833

output:

505929170 38979522 -234517643 779426335 -195538121 740446813 544908692

result:

ok Answer is correct

Test #24:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

477032252615296225 108870012374411737 333393233802837749 701555474043722237

output:

690675215 -324002404 -62389539 429062350 -386391943 753064754 366672811

result:

ok Answer is correct

Test #25:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

1299556716903225 355747388532580098 692024059544933421 337576227729256548

output:

36049365 -540431757 -252350757 -252031635 -792782514 288400122 -504382392

result:

ok Answer is correct

Test #26:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

65258206810145881 521153173952727205 930630862422604093 474735895280022769

output:

255456859 -653356447 -307048086 -90851502 -960404533 562504945 -397899588

result:

ok Answer is correct

Test #27:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

8131402216306944 151743259973886485 212869615963839370 69257758206259829

output:

90174288 -304122658 243418711 -457367081 -60703947 -153244423 -213948370

result:

ok Answer is correct

Extra Test:

score: 0
Extra Test Passed