Hướng dẫn giải của Pháo và bóng bay (bản thanh niên)

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người làm lời giải.


Nộp code mẫu trước khi tự giải được bài tập là một hành vi có thể bị ban.

Ta có thể xác định được mặt cầu như sau:

  • Gọi phương trình mặt cầu: ~x^2 + y^2 + z^2 + 2ax + 2by + 2cz + d = 0~
  • Ta có ~x, y, z~ là tọa độ các điểm mà đề cho, vậy ta chỉ cần xác định ~a, b, c, d~.

Đến đây bài toán đã trở thành Giải hệ phương trình ~4~ ẩn, với ràng buộc không có ~4~ điểm bất kì đồng phẳng, ta hoàn toàn có thể giải bài này bằng phương pháp Khử Gauss .

Code tham khảo

                    // Template //
                //Author: kieuphat159//
//******************************************************************//
#include <bits/stdc++.h>
#define FOR(i, a, b) for(ll i=a, _b=b; i<=_b; i++)
#define FORD(i, a, b) for(ll i=a, _b=b; i>=_b; i--)
#define pb push_back
#define ALL(a) a.begin(), a.end()
#define mp make_pair
#define fi first
#define se second
#define mset(a, b) memset(a, b, sizeof(a))
#define BIT(x, i) ((x>>i)&1)
#define MASK(i) (1LL<<(i))
#define all(a, n) a+1, a+1+n

using namespace std;
typedef int64_t ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef pair<ll, ii> iii;
const ll maxn = 1e5 + 5;
const ll mod = 1e9+7;
const ll inf = 1e18;
const ll base = 37;
const ld eps = 1e-10;

template<class T>
    bool minimize(T &a, T b){
        return a>b ? a=b, true : false;
    }

template<class T>
    bool maximize(T &a, T b){
        return a<b ? a=b, true : false;
    }

ll POW(ll a, ll b)
{
    if (b==0) return 1;
    if (b==1) return a;
    ll tmp=POW(a, b/2) % mod;
    return b%2==0 ? (tmp * tmp)%mod : (((tmp*tmp)%mod)*a)%mod;
}
//******************************************************************//



                    // Main Function //
//******************************************************************//
ll n;
ld xp, yp, zp;
ld x[maxn][4];
ld a[5][5], tmp[5][5];

#define sq(x) (x)*(x)

void input()
{
    cin>>n>>xp>>yp>>zp;
    FOR(i, 1, n) FOR(j, 1, 3) cin>>x[i][j];
}

void cop(bool ok)
{
    if (ok){
        FOR(i, 1, 4) FOR(j, 1, 5) tmp[i][j] = a[i][j];
    }
    else FOR(i, 1, 4) FOR(j, 1, 5) a[i][j] = tmp[i][j];
}

void solve()
{
        // Sắp xếp các số thành hệ phương trình 4 ẩn vào mảng a\\
//----------------------------------------------------------------------\\

    ld y[5];
    y[1] = sq(x[1][1]) + sq(x[1][2]) + sq(x[1][3]);
    y[2] = sq(x[2][1]) + sq(x[2][2]) + sq(x[2][3]);
    y[3] = sq(x[3][1]) + sq(x[3][2]) + sq(x[3][3]);
    y[4] = sq(x[4][1]) + sq(x[4][2]) + sq(x[4][3]);

//    -2*x[1][1] -2*x[1][2] -2*x[1][3] + b = -y[1]
//    -2*x[2][1] -2*x[2][2] -2*x[2][3] + b = -y[2]
//    -2*x[3][1] -2*x[3][2] -2*x[3][3] + b = -y[3]
//    -2*x[4][1] -2*x[4][2] -2*x[4][3] + b = -y[4]


    FOR(i, 1, 4) FOR(j, 1, 3) a[i][j] = -2*x[i][j];
    FOR(i, 1, 4) a[i][4] = 1;
    FOR(i, 1, 4) a[i][5] = -y[i];
//-----------------------------------------------------------------------\\



                    // Khử Gauss\\
//--------------------------------------------------------------------\\

    cop(1); //copy a --> tmp

    FOR(i, 2, 4)
    {
        ld times = a[i][1] / a[1][1];
        FOR(j, 1, 5) tmp[i][j] = -times*a[1][j] + a[i][j];
    }

    cop(0); //copy tmp --> a

    FOR(i, 3, 4)
    {
        ld times = a[i][2] / a[2][2];
        FOR(j, 1, 5) tmp[i][j] = -times*a[2][j] + a[i][j];
    }

    cop(0); // copy tmp --> a

    ld times = a[4][3] / a[3][3];
    FOR(i, 1, 5) tmp[4][i] = -times*a[3][i] + a[4][i];

    cop(0); // copy tmp --> a
//------------------------------------------------------------------\\


                //Sau khi khử, xác định 4 ẩn số\\
            //Trong đó, x1, x2, x3 là tọa độ tâm\\
//-------------------------------------------------------------------\\

    ld x4 = a[4][5]/a[4][4];
    ld x3 = (a[3][5] - a[3][4]*x4)/a[3][3];
    ld x2 = (a[2][5] - a[2][4]*x4 - a[2][3]*x3)/a[2][2];
    ld x1 = (a[1][5] - x4*a[1][4] - x3*a[1][3] - x2*a[1][2])/a[1][1];
//--------------------------------------------------------------------\\



                // Tính kết quả cuối cùng\\
//---------------------------------------------------------------------\\

    ld R = sqrt(sq(x3) + sq(x2) + sq(x1) - x4);
    ld dist = sqrt(sq(xp-x1) + sq(yp-x2) + sq(zp-x3));
    ld ans = dist - R;
    cout<<setprecision(2)<<fixed<<ans;
//----------------------------------------------------------------------\\

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #define task ""
//    freopen(task".INP", "r", stdin);
//    freopen(task".OUT", "w", stdout);
    int test_case=1; //cin>>test_case;
    while(test_case--)
    {
        input(), solve();
        cout<<'\n';
    }
    return 0;
}
//******************************************************************//

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.