QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #234603 | #6524. Final Defense Line | ucup-team1198 | WA | 548ms | 3864kb | C++20 | 6.5kb | 2023-11-01 19:41:32 | 2023-11-01 19:41:32 |
Judging History
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) {
assert(a.q > 0 && b.q > 0);
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) {
alpha = alpha - Rat(xa, 1);
Rat A = beta * beta - Rat(1, 1);
Rat B = Rat(2 * da, 1) + Rat(2, 1) * alpha * beta;
Rat C = alpha * alpha - Rat(da * da, 1);
if (A == 0 && B == 0) {
if (C == 0) {
cout << "-1\n";
return;
}
cout << "0\n";
return;
}
if (A == 0) {
cout << "-1\n";
return;
}
if (A > 0) {
cout << "-1\n";
return;
}
Rat x = -B / (Rat(2, 1) * A);
if (x * x * A + x * B + C < 0) {
cout << "0\n";
return;
}
if (x * x * A + x * B + C == 0) {
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 <= 0 && val * val >= D) {
if (D == 0) {
cout << "1 ";
} else {
cout << "2 ";
is_minus = true;
}
} else if (val <= 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";
}
cout << "-1\n";
return;
}
cout << "0\n";
return;
}
Rat r = -gamma / delta;
assert(r.q != 0);
if (r < minr) {
cout << "0\n";
return;
}
Rat x = alpha + r * beta;
assert(x.q != 0);
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 <= 0 && val * val >= D) {
if (D == 0) {
cout << "1 ";
} else {
cout << "2 ";
is_minus = true;
}
} else if (val <= 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: 0ms
memory: 3796kb
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: 548ms
memory: 3864kb
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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer case #2976 differ - expected: 1, found: 0