QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#109378 | #6524. Final Defense Line | SSRS | AC ✓ | 154ms | 3748kb | C++17 | 4.5kb | 2023-05-28 19:55:53 | 2023-05-28 19:55:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(10);
int T;
cin >> T;
for (int i = 0; i < T; i++){
int xa, ya, da;
cin >> xa >> ya >> da;
int xb, yb, db;
cin >> xb >> yb >> db;
int xc, yc, dc;
cin >> xc >> yc >> dc;
if (xa < xb){
swap(xa, xb);
swap(ya, yb);
swap(da, db);
}
int mx = max({da, db, dc});
da -= mx;
db -= mx;
dc -= mx;
long long a11 = -2 * (xb - xa);
long long a12 = 0;
long long a13 = 2 * (db - da);
long long a21 = -2 * (xc - xa);
long long a22 = -2 * yc;
long long a23 = 2 * (dc - da);
long long b1 = db * db - xb * xb - da * da + xa * xa;
long long b2 = dc * dc - xc * xc - yc * yc - da * da + xa * xa;
if (yc == 0){
long long det = a11 * a23 - a13 * a21;
if (det != 0){
long long xn = b1 * a23 - a13 * b2;
long long rn = a11 * b2 - b1 * a21;
if (rn < 0 && det > 0 || rn > 0 && det < 0){
cout << 0 << '\n';
} else {
long long Y = (rn - da * det) * (rn - da * det) - (xn - xa * det) * (xn - xa * det);
if (Y == 0){
cout << 1 << ' ' << mx + (double) rn / det << '\n';
} else if (Y > 0){
cout << 2 << ' ' << mx + (double) rn / det << '\n';
} else {
cout << 0 << '\n';
}
}
} else {
long long A = a11 * a11 - a13 * a13;
long long B = -2 * a11 * a11 * da - 2 * a13 * (a11 * xa - b1);
long long C = a11 * a11 * da * da - (a11 * xa - b1) * (a11 * xa - b1);
//Ar^2+Br+C=a11^2*y^2
if (A > 0){
cout << -1 << '\n';
} else if (A < 0){
if (C > 0){
cout << -1 << '\n';
} else if (C == 0){
if (B > 0){
cout << -1 << '\n';
} else {
cout << 1 << ' ' << mx << '\n';
}
} else {
long long D = B * B - 4 * A * C;
if (D > 0){
if (B > 0){
cout << -1 << '\n';
} else {
cout << 0 << '\n';
}
} else if (D == 0){
if (B < 0){
cout << 1 << ' ' << mx + (double) -B / (A * 2) << '\n';
} else {
cout << 0 << '\n';
}
} else {
cout << 0 << '\n';
}
}
} else if (B != 0){
if (B > 0 || B < 0 && C > 0){
cout << -1 << '\n';
} else if (B < 0 && C == 0){
cout << 1 << ' ' << mx << '\n';
} else {
cout << 0 << '\n';
}
} else {
if (C >= 0){
cout << -1 << '\n';
} else {
cout << 0 << '\n';
}
}
}
} else {
long long det = a11 * a22 - a12 * a21;
long long p1 = a22 * (-a13) + (-a12) * (-a23);
long long q1 = a22 * b1 + (-a12) * b2;
long long p2 = (-a21) * (-a13) + a11 * (-a23);
long long q2 = (-a21) * b1 + a11 * b2;
long long A = p1 * p1 + p2 * p2 - det * det;
long long B = 2 * p1 * (q1 - xa * det) + 2 * p2 * q2 - 2 * det * det * (-da);
long long C = (q1 - xa * det) * (q1 - xa * det) + q2 * q2 - det * det * da * da;
//Ar^2+Br+C=0
if (A != 0){
if (A < 0){
A *= -1;
B *= -1;
C *= -1;
}
__int128_t D = (__int128_t) B * B - (__int128_t) 4 * A * C;
if (D < 0){
cout << 0 << '\n';
} else if (D == 0){
if (B <= 0){
cout << 1 << ' ' << mx + (double) -B / (A * 2) << '\n';
} else {
cout << 0 << '\n';
}
} else {
if (C >= 0 && B < 0){
cout << 2 << ' ' << mx + (-B - sqrt((double) D)) / (A * 2) << '\n';
} else if (C == 0 && B < 0 || C <= 0){
cout << 1 << ' ' << mx + (-B + sqrt((double) D)) / (A * 2) << '\n';
} else {
cout << 0 << '\n';
}
}
} else if (B != 0){
if (B > 0 && C <= 0 || B < 0 && C >= 0){
cout << 1 << ' ' << mx + (double) -C / B << '\n';
} else {
cout << 0 << '\n';
}
} else if (C != 0){
cout << 0 << '\n';
} else {
cout << -1 << '\n';
}
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3568kb
input:
2 0 0 1 3 0 2 10 2 2 0 0 1 3 0 2 10 2 -2
output:
2 10.3273292135 2 5.3417307854
result:
ok 2 cases
Test #2:
score: 0
Accepted
time: 154ms
memory: 3748kb
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:
ok 200000 cases