HackerRank Algebra - The Axis of Awesome - Asociația „Investește pentru Viitorul Tău” Buzău

Challenge: The Axis of Awesome

Subdomeniu: Algebra (algebra)

Scor cont: 80.0 / 80

Submission status: Accepted

Submission score: 1.0

Submission ID: 464780760

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/the-axis-of-awesome/problem

Cerinta

Jack Skellington kidnapped Sandy Claws so he can replace him on Christmas! The monsters of Halloween Town are helping Jack make toys for all the children.  

One of these toys is a special kind of gyroscopic exercise tool. It consists of $n$ balls that levitate around the center of the toy. To play with it, a child chooses some axis passing through the center and begins to rotate all the balls around it simultaneously. The effort needed to perform the exercise is proportional to the sum of squared distances from every ball to the chosen axis. If the needed effort for this axis is not less than for any other one, we call it *The Axis of Awesome*. Now Jack wants to improve these gyroscopic toys by adding zero or more balls to each toy so that every possible axis of play was an Axis of Awesome.

You are given the blueprints for $t$ gyroscopic toys, where each toy is described as a set of $n$ three-dimensional $(x, y, z)$ coordinates denoting the locations of the toy's balls. For each toy, find the the minimum number of balls Jack must add so that any possible axis would be called Axis of Awesome. If no amount of additional balls makes this possible, print `-1` instead.

**Note:** The center of each toy is always located at point $(0, 0, 0)$.

Input Format

The first line contains an integer, $t$, denoting the number of gyroscopic toys. The subsequent lines describe each toy in the following format:	

1. The first line contains an integer, $n$, denoting the number of balls in the toy.
2. Each of the $n$ subsequent lines contain $3$ space-separated integers describing the respective $x$, $y$, and $z$ coordinates of one of the toy's balls.

Output Format

For each toy, print a single integer on a new line denoting the minimum number of balls Jack must add to the toy so that the effort to play with it is always maximal; if this is not possible, print `-1` instead.

Constraints

+ $1 \leq t \leq 5000$  
+ $1 \leq n \leq 100$  
+ $-50 \leq x,y,z \leq 50$
- Different balls *may* have the same coordinates.

Cod sursa

#include <bits/stdc++.h>
using namespace std;

static inline long double sq(long double x){ return x*x; }

// Jacobi eigenvalues for symmetric 3x3
array<long double,3> eigen_sym_3x3(long double A[3][3]) {
    for(int it=0; it<60; it++){
        int p=0,q=1;
        long double mx = fabsl(A[0][1]);
        if(fabsl(A[0][2]) > mx){ mx=fabsl(A[0][2]); p=0;q=2; }
        if(fabsl(A[1][2]) > mx){ mx=fabsl(A[1][2]); p=1;q=2; }
        if(mx < 1e-18L) break;

        long double app=A[p][p], aqq=A[q][q], apq=A[p][q];
        long double phi = 0.5L * atan2l(2*apq, aqq-app);
        long double c = cosl(phi), s = sinl(phi);

        // rotate
        long double Bpp = c*c*app - 2*s*c*apq + s*s*aqq;
        long double Bqq = s*s*app + 2*s*c*apq + c*c*aqq;
        A[p][p]=Bpp; A[q][q]=Bqq;
        A[p][q]=A[q][p]=0;

        for(int r=0;r<3;r++){
            if(r==p||r==q) continue;
            long double arp=A[r][p], arq=A[r][q];
            A[r][p]=A[p][r]=c*arp - s*arq;
            A[r][q]=A[q][r]=s*arp + c*arq;
        }
    }
    return {A[0][0], A[1][1], A[2][2]};
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    while(T--){
        int n; cin >> n;
        long double I[3][3] = {{0,0,0},{0,0,0},{0,0,0}};
        for(int i=0;i<n;i++){
            long double x,y,z; cin >> x >> y >> z;
            // inertia tensor: [[y^2+z^2, -xy, -xz], ...]
            I[0][0] += y*y + z*z;
            I[1][1] += x*x + z*z;
            I[2][2] += x*x + y*y;
            I[0][1] -= x*y; I[1][0] -= x*y;
            I[0][2] -= x*z; I[2][0] -= x*z;
            I[1][2] -= y*z; I[2][1] -= y*z;
        }

        auto eig = eigen_sym_3x3(I);
        sort(eig.begin(), eig.end());

        long double eps = 1e-10L * max((long double)1.0L, fabsl(eig[2]));
        int m = 1;
        if(fabsl(eig[1]-eig[0]) <= eps) m++;
        if(fabsl(eig[2]-eig[0]) <= eps) m++; // all equal
        // m is multiplicity of smallest eigenvalue (eig[0])

        cout << (3 - m) << "\n";
    }
    return 0;
}

HackerRank Algebra – The Axis of Awesome