QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#109378#6524. Final Defense LineSSRSAC ✓154ms3748kbC++174.5kb2023-05-28 19:55:532023-05-28 19:55:55

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-28 19:55:55]
  • 评测
  • 测评结果:AC
  • 用时:154ms
  • 内存:3748kb
  • [2023-05-28 19:55:53]
  • 提交

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