QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#513039#9168. Square Locatorucup-team4361#AC ✓1ms3728kbC++143.4kb2024-08-10 16:42:052024-08-10 16:42:05

Judging History

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

  • [2024-08-10 16:42:05]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3728kb
  • [2024-08-10 16:42:05]
  • 提交

answer

#include <bits/stdc++.h>

#define LL long long
#define ull unsigned long long
#define F(i, j, k) for (int i = j; i <= k; ++i)
#define DF(i, j, k) for (int i = j; i >= k; --i)

using namespace std;

template <typename T> inline void read(T &n) {
    T w = 1;
    n = 0;
    char ch = getchar();
    while (!isdigit(ch) && ch != EOF) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (isdigit(ch) && ch != EOF) {
        n = (n << 3) + (n << 1) + (ch & 15);
        ch = getchar();
    }
    n *= w;
}

template <typename T> inline void write(T x) {
    T l = 0;
    ull y = 0;
    if (!x) { putchar(48); return; }
    if (x < 0) { x = -x; putchar('-'); }
    while (x) { y = y * 10 + x % 10; x /= 10; ++l; }
    while (l) { putchar(y % 10 + 48); y /= 10; --l; }
}

template <typename T> inline void writes(T x) {
    write(x);
    putchar(' ');
}

template <typename T> inline void writeln(T x) {
    write(x);
    puts("");
}

template <typename T> inline void checkmax(T &a, T b) { a = a > b ? a : b; }

template <typename T> inline void checkmin(T &a, T b) { a = a < b ? a : b; }

const double Eps = 1e-8;

bool f = 0;

LL A, B, C, D;

inline double check(double now) {
    double xa = 0, ya = sqrt(A);
    double csita = (D - A - now * now) / (2.0 * sqrt(A) * now);
    double yd = ya + csita * now;
    double xd = sqrt(now * now - csita * now * csita * now);
    double xb1 = yd - ya, yb1 = ya - xd;
    double xb2 = ya - yd, yb2 = ya + xd;
    return min(xb1 * xb1 + yb1 * yb1, xb2 * xb2 + yb2 * yb2);
}

int swp = 0;

inline void work(double now) {
    double xa = 0, ya = sqrt(A);
    double csita = (D - A - now * now) / (2.0 * sqrt(A) * now);
    double yd = ya + csita * now;
    double xd = sqrt(now * now - csita * now * csita * now);
    double xb1 = yd - ya, yb1 = ya - xd;
    double xb2 = ya - yd, yb2 = ya + xd;
    double xb, yb;
    if (xb1 * xb1 + yb1 * yb1 < xb2 * xb2 + yb2 * yb2) {
        xb = xb1;
        yb = yb1;
    }
    else {
        xb = xb2;
        yb = yb2;
    }
    double xc = xb + xd - xa, yc = yb + yd - ya;
    if ((LL)round(xc) * (LL)round(xc) + (LL)round(yc) * (LL)round(yc) == C
    && (round(xa) != round(xb) || round(ya) != round(yb)))
    {
        f = 1;
        if (swp) {
            swap(xb, xd);
            swap(yb, yd);
        }
        cout << (LL)round(ya) << ' ';
        cout << (LL)round(xb) << ' ' << (LL)round(yb) << ' ';
        cout << (LL)round(xc) << ' ' << (LL)round(yc) << ' ';
        cout << (LL)round(xd) << ' ' << (LL)round(yd) << '\n';
        exit(0);
    }
}

int main() {
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    cin >> A >> B >> C >> D;
    if (B > D) {
        swap(B, D);
        swp = 1;
    }
    double l = fabs(sqrt(A) - sqrt(D)) + Eps, r = sqrt(A) + sqrt(D) - Eps;
    F(i, 1, 1000) {
        double mid1 = l + (r - l) / 3.0, mid2 = r - (r - l) / 3.0;
        if (check(mid1) < check(mid2)) r = mid2;
        else l = mid1;
    }
    double true_mid = l;
    l = fabs(sqrt(A) - sqrt(D)) + Eps, r = true_mid;
    F(i, 1, 1000) {
        double mid = (l + r) / 2.0;
        if (check(mid) > B) l = mid;
        else r = mid;
    }
    work(l);
    l = true_mid, r = sqrt(A) + sqrt(D) - Eps;
    F(i, 1, 1000) {
        double mid = (l + r) / 2.0;
        if (check(mid) < B) l = mid;
        else r = mid;
    }
    work(l);
    if (!f) assert(0);
    return 0;
}

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

详细

Test #1:

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

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: 3600kb

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: 3672kb

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: 3544kb

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: 3688kb

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: 3616kb

input:

9 16 65 58

output:

3 4 0 7 4 3 7

result:

ok Answer is correct

Test #7:

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

input:

25 13 101 113

output:

5 3 -2 10 1 7 8

result:

ok Answer is correct

Test #8:

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

input:

16 25 58 49

output:

4 3 4 3 7 0 7

result:

ok Answer is correct

Test #9:

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

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: 3604kb

input:

126736 551200 1838608 1414144

output:

356 732 -124 1212 608 480 1088

result:

ok Answer is correct

Test #11:

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

input:

6007401 6936277 5051405 4122529

output:

2451 426 2599 574 2173 148 2025

result:

ok Answer is correct

Test #12:

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

input:

2209 2536706 4875777 2341280

output:

47 691 1435 2079 744 1388 -644

result:

ok Answer is correct

Test #13:

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

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: 3656kb

input:

722790729241 782340801290 3904082690373 3844532618324

output:

850171 881809 -68947 1800927 812862 919118 1731980

result:

ok Answer is correct

Test #15:

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

input:

3870332944 287487526720 654504136912 370886943136

output:

62212 530544 -77528 670284 453016 139740 592756

result:

ok Answer is correct

Test #16:

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

input:

42230661001 2038831296200 3308981375377 1312380740178

output:

205501 771514 1201498 1767511 429984 995997 -566013

result:

ok Answer is correct

Test #17:

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

input:

132551656347532249 102473514386838101 439829344402853445 469907486363547593

output:

364076443 285439930 144905351 504611022 430345281 219171092 649516373

result:

ok Answer is correct

Test #18:

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

input:

55636209407170681 109515374676898429 329424831462677605 275545666192949857

output:

235873291 284729573 168654810 351948054 453384383 67218481 520602864

result:

ok Answer is correct

Test #19:

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

input:

466589422796014144 325095618166198298 43553814262839476 185047618892655322

output:

683073512 301902073 483684563 102513124 181782490 -199388949 381171439

result:

ok Answer is correct

Test #20:

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

input:

6909562468993284 229067899424048957 357610810027741258 135452473072685585

output:

83123778 222468866 423763499 563108587 201294633 340639721 -139345088

result:

ok Answer is correct

Test #21:

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

input:

5000019216542596 408275955794662066 885792080806957480 482516144228838010

output:

70710814 -163457821 -617703405 524956398 -781161226 688414219 -92747007

result:

ok Answer is correct

Test #22:

score: 0
Accepted
time: 1ms
memory: 3556kb

input:

1736111972222329 40264917317940640 105455671025820505 66926865680102194

output:

41666677 166940988 -111335636 319943301 55605352 153002313 208607665

result:

ok Answer is correct

Test #23:

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

input:

255964325056888900 56517928013623933 645740568455742866 845186965499007833

output:

505929170 234517643 -38979522 779426335 195538121 544908692 740446813

result:

ok Answer is correct

Test #24:

score: 0
Accepted
time: 1ms
memory: 3728kb

input:

477032252615296225 108870012374411737 333393233802837749 701555474043722237

output:

690675215 62389539 324002404 429062350 386391943 366672811 753064754

result:

ok Answer is correct

Test #25:

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

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: 3720kb

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: 3688kb

input:

8131402216306944 151743259973886485 212869615963839370 69257758206259829

output:

90174288 243418711 304122658 457367081 60703947 213948370 -153244423

result:

ok Answer is correct

Extra Test:

score: 0
Extra Test Passed