QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#513018#9168. Square Locatorucup-team4361#WA 1ms3672kbC++143.3kb2024-08-10 16:37:482024-08-10 16:37:49

Judging History

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

  • [2024-08-10 16:37:49]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3672kb
  • [2024-08-10 16:37:48]
  • 提交

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);
}

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;
        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);
    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;
}

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 -1 2 3 1 4 5

result:

ok Answer is correct

Test #2:

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

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

input:

1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000

output:

1000000000 -1000000000 0 0 -1000000000 1000000000 0

result:

ok Answer is correct

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3620kb

input:

4 10 8 2

output:

2 1 1 2 2 1 3

result:

wrong answer Squared distances are incorrect