QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#234542#6524. Final Defense Lineucup-team1198#WA 597ms3684kbC++204.3kb2023-11-01 19:03:122023-11-01 19:03:13

Judging History

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

  • [2023-11-01 19:03:13]
  • 评测
  • 测评结果:WA
  • 用时:597ms
  • 内存:3684kb
  • [2023-11-01 19:03:12]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()

using i128 = __int128;

i128 gcd(i128 a, i128 b) {
    while (b != 0) {
        a %= b;
        swap(a, b);
    }
    return a;
}

struct Rat {
    i128 p;
    i128 q;

    Rat(i128 p = 0, i128 q = 1): p(p), q(q) {} 

    Rat norm() {
        i128 d = gcd(p, q);
        p /= d;
        q /= d;
        if (q < 0) {
            q *= -1;
            p *= -1;
        }
        return *this;
    }

    ld out() {
        return (ld)p / q;
    }
};

Rat operator*(const Rat& a, const Rat& b) {
    return Rat(a.p * b.p, a.q * b.q).norm();
}

Rat operator-(const Rat& a) {
    return Rat(-a.p, a.q);
}

Rat operator/(const Rat& a, const Rat& b) {
    return Rat(a.p * b.q, b.p * a.q).norm();
}

Rat operator+(const Rat& a, const Rat& b) {
    i128 d = gcd(a.q, b.q);
    i128 q = a.q / d * b.q;
    return Rat(b.q / d * a.p + a.q / d * b.p, q).norm();
}

Rat operator-(const Rat& a, const Rat& b) {
    return a + (-b);
}

bool operator==(const Rat& a, const Rat& b) {
    return a.p * b.q == a.q * b.p;
}

bool operator<(const Rat& a, const Rat& b) {
    return a.p * b.q < a.q * b.p;
}

bool operator>(const Rat& a, const Rat& b) {
    return b < a;
}

bool operator<=(const Rat& a, const Rat& b) {
    return !(b < a);
}

bool operator>=(const Rat& a, const Rat& b) {
    return !(a < b);
}

Rat abs(const Rat& x) {
    if (x.p >= 0) return x;
    return -x;
}

void solve() {
    int xa, da, xb, db, xc, yc, dc;
    int useless;
    cin >> xa >> useless >> da >> xb >> useless >> db >> xc >> yc >> dc;
    Rat minr = Rat(max(da, max(db, dc)), 1);
    Rat alpha = Rat(xa + xb, 2) + Rat(da * da - db * db, 2 * xb - 2 * xa);
    alpha.norm();
    Rat beta = Rat(db - da, xb - xa);
    beta.norm();
    /// cout << alpha.out() << " " << beta.out() << endl;
    Rat gamma = Rat(da * da - dc * dc + xc * xc - xa * xa + yc * yc, 1) - alpha * Rat(2 * xc - 2 * xa, 1);
    Rat delta = Rat(2 * dc - 2 * da, 1) - beta * Rat(2 * xc - 2 * xa, 1);
    if (yc == 0) {
        if (delta == Rat(0, 1)) {
            if (gamma == 0) {
                cout << "-1\n";
                return;
            }
            cout << "0\n";
            return;
        }
        Rat r = -gamma / delta;
        if (r < minr) {
            cout << "0\n";
            return;
        }
        Rat x = alpha + r * beta;
        Rat lft = abs(x - Rat(xa, 1)), rgh = abs(r - Rat(da, 1));
        if (lft > rgh) {
            cout << "0\n";
            return;
        }
        if (lft == rgh) {
            cout << 1 << " ";
        } else {
            cout << 2 << " ";
        }
        cout << r.out() << "\n";
        return;
    }
    gamma = gamma / Rat(2 * yc, 1);
    delta = delta / Rat(2 * yc, 1);
    Rat A = Rat(1, 1) - beta * beta - delta * delta;
    Rat B = Rat(-2, 1) * (Rat(da, 1) + gamma * delta + alpha * beta);
    Rat C = Rat(da * da, 1) - alpha * alpha - gamma * gamma;

    if (A == 0) {
        if (B == 0) {
            if (C == 0) {
                cout << "-1\n";
                return;
            }
            cout << "0\n";
            return;
        }
        Rat r = -C / B;
        if (r < minr) {
            cout << "0\n";
            return;
        }
        cout << 1 << " " << r.out() << "\n";
        return;
    }

    Rat D = B * B - A * C * Rat(4, 1);
    if (D < 0) {
        cout << "0\n";
        return;
    }
    if (A < 0) {
        A = -A;
        B = -B;
        C = -C;
    }
    Rat val = minr * A * Rat(2, 1) + B;
    bool is_minus = false;
    if (val <= Rat(0, 0) && val * val >= D) {
        if (D == 0) {
            cout << "1 ";
        } else {
            cout << "2 ";
            is_minus = true;
        }
    } else if (val <= Rat(0, 0)) {
        cout << "1 ";
    } else if (val * val <= D) {
        cout << "1 ";
    } else {
        cout << "0\n";
        return;
    }
    ld ans = -B.out();
    if (is_minus) {
        ans -= sqrtl(D.out());
    } else {
        ans += sqrtl(D.out());
    }
    ans /= 2 * A.out();
    cout << ans << "\n";
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cout << fixed << setprecision(20);

    int tst;
    cin >> tst;
    while (tst--) {
        solve();
    }

    return 0;
}

详细

Test #1:

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

input:

2
0 0 1
3 0 2
10 2 2
0 0 1
3 0 2
10 2 -2

output:

2 10.32732921346864029578
2 5.34173078544039510885

result:

ok 2 cases

Test #2:

score: -100
Wrong Answer
time: 597ms
memory: 3684kb

input:

200000
10 0 30
0 0 20
-50 0 2
10 0 30
0 0 20
-50 0 -2
10 0 30
0 0 20
-50 1 2
10 0 30
0 0 20
-50 1 -2
10 0 30
0 0 20
-50 2 2
10 0 30
0 0 20
-50 2 -2
10 0 30
0 0 20
-50 3 2
10 0 30
0 0 20
-50 3 -2
10 0 30
0 0 20
-50 4 2
10 0 30
0 0 20
-50 4 -2
10 0 30
0 0 20
-50 5 2
10 0 30
0 0 20
-50 5 -2
10 0 30
0 0...

output:

0
0
2 -14.89838506553950917780
2 -17.05361595913051806633
2 -15.84892728487070638361
2 -18.17026859595811000107
2 -16.85299895515169685267
2 -19.35176476068823746973
2 -17.91196519985580117885
2 -20.59990069393440159130
2 -19.02718047995810614348
2 -21.91645688469071452664
2 -20.19998522019807815110...

result:

wrong answer case #3 differ - expected: 0, found: 2