## 1. Abridged Problem Statement

Given `n ≤ 100` star systems in 3D space, each with a possibly space-containing name and integer coordinates, determine which stars must have laser control towers.

The laser net should cover the surface of the convex hull of all stars. Any star lying on that surface — as a vertex, on an edge, or inside a hull face — must have a tower. Stars strictly inside the 3D convex hull do not.

Output the number of such stars and their names in alphabetical order.

If all stars are degenerate, e.g. lie on a line or plane, every star is considered to be on the boundary and needs a tower.

---

## 2. Detailed Editorial

### Key observation

The desired laser net surrounds the convex hull of all star systems. Therefore:

- A star strictly inside the convex hull is not touched by the laser surface.
- A star on the boundary of the convex hull is touched by some hull face and needs a tower.

So the task is:

> Find all input points that lie on the boundary of the 3D convex hull.

Names of those points are printed alphabetically.

---

### Geometry primitive: signed volume

For four points `a, b, c, d`, define:

\[
V(a,b,c,d) = ((b-a) \times (c-a)) \cdot (d-a)
\]

This is six times the signed volume of tetrahedron `abcd`.

Properties:

- `V = 0` means the four points are coplanar.
- The sign tells which side of plane `abc` point `d` lies on.
- Since all coordinates are integers, exact integer arithmetic can be used.

---

### Degenerate cases

If the set of points is not truly 3-dimensional:

- fewer than 4 points,
- all points equal,
- all points collinear,
- all points coplanar,

then the convex hull has dimension `0`, `1`, or `2`.

In that case, every star lies on the boundary of the hull, so all names are printed.

The C++ solution detects this while trying to construct an initial tetrahedron.

---

### QuickHull in the provided C++ solution

The provided solution uses a 3D QuickHull algorithm.

Each hull face stores:

```cpp
array<int, 3> v;       // indices of its 3 vertices
array<int, 3> nbr;     // neighboring faces across each edge
vector<int> outside;   // points known to lie outside this face
bool alive;            // whether this face still belongs to the current hull
```

The algorithm works as follows.

---

### Step 1: Build an initial tetrahedron

The algorithm finds four non-coplanar points:

1. `i0`: first point.
2. `i1`: first point different from `i0`.
3. `i2`: first point not collinear with `i0, i1`.
4. `i3`: first point not coplanar with `i0, i1, i2`.

If any of these does not exist, the point set is degenerate.

Otherwise, these four points form an initial tetrahedron.

The faces are oriented so that their normals point outward.

---

### Step 2: Assign outside points

For every remaining point, the algorithm checks whether it lies outside one of the tetrahedron faces.

A point is outside face `f` if:

```cpp
signed_volume(face_vertices, point) > 0
```

Such points are stored in the corresponding face’s `outside` list.

---

### Step 3: Expand the hull

While there exists a face with outside points:

1. Pick the farthest outside point from that face.  
   This point becomes the new hull vertex, called `apex`.

2. Find all faces visible from `apex`.  
   A face is visible if `apex` lies outside it.

3. The boundary between visible and non-visible faces is called the horizon.

4. Delete all visible faces.

5. For every horizon edge, create a new triangular face connecting that edge to `apex`.

6. Reconnect neighbor pointers.

7. Redistribute points that used to belong to deleted faces among the new faces.

Eventually no face has outside points, so the convex hull is complete.

---

### Step 4: Determine boundary points

For each input point `p`, the solution checks all alive hull faces.

If for some hull face `(a,b,c)`:

```cpp
signed_volume(a, b, c, p) == 0
```

then `p` lies on the supporting plane of a hull face.

Since all input points lie inside or on the convex hull, lying on a supporting plane means the point is on the hull boundary.

Therefore, that star needs a tower.

---

### Complexity

For `n ≤ 100`, QuickHull is easily fast enough.

The worst-case theoretical complexity of QuickHull can be high, but for this problem size it is practical.

The exact arithmetic uses 64-bit signed integers. Coordinates are at most `10000` by absolute value, so signed volumes safely fit in `int64_t`.

---

## 3. Provided C++ Solution with Detailed Comments

```cpp
#include <bits/stdc++.h> // Includes almost all standard C++ library headers.

using namespace std; // Allows using standard names without std:: prefix.

// Output operator for pairs, useful for debugging or generic printing.
template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

// Input operator for pairs.
template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

// Input operator for vectors.
// Reads every element of the vector.
template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

// Output operator for vectors.
// Prints elements separated by spaces.
template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

// Coordinate type.
// int64_t is used because signed volumes may be much larger than coordinates.
using coord_t = int64_t;

// Represents a point or vector in 3D.
struct Point3D {
    coord_t x, y, z; // Cartesian coordinates.

    // Constructor with default value (0, 0, 0).
    Point3D(coord_t x = 0, coord_t y = 0, coord_t z = 0) : x(x), y(y), z(z) {}

    // Vector addition.
    Point3D operator+(const Point3D& p) const {
        return {x + p.x, y + p.y, z + p.z};
    }

    // Vector subtraction.
    Point3D operator-(const Point3D& p) const {
        return {x - p.x, y - p.y, z - p.z};
    }

    // Cross product of two 3D vectors.
    Point3D cross(const Point3D& p) const {
        return {
            y * p.z - z * p.y,
            z * p.x - x * p.z,
            x * p.y - y * p.x
        };
    }

    // Dot product of two 3D vectors.
    coord_t dot(const Point3D& p) const {
        return x * p.x + y * p.y + z * p.z;
    }

    // Equality test for points.
    bool operator==(const Point3D& p) const {
        return x == p.x && y == p.y && z == p.z;
    }

    // Computes six times the signed volume of tetrahedron abcd.
    //
    // Positive/negative sign tells which side of plane abc point d lies on.
    // Zero means a, b, c, d are coplanar.
    friend coord_t signed_volume(
        const Point3D& a,
        const Point3D& b,
        const Point3D& c,
        const Point3D& d
    ) {
        return (b - a).cross(c - a).dot(d - a);
    }
};

// 3D QuickHull implementation.
class QuickHull3D {
  public:
    // One triangular face of the hull.
    struct Face {
        array<int, 3> v;       // Indices of the 3 vertices of the face.
        array<int, 3> nbr;     // Neighboring face indices across each edge.
        vector<int> outside;   // Points currently known to be outside this face.
        bool alive;            // False if the face has been removed.
    };

    vector<Point3D> points; // All input points.
    vector<Face> faces;     // All faces ever created.
    bool degenerate;        // True if the hull is not 3-dimensional.

    // Constructor stores points and immediately builds the hull.
    QuickHull3D(const vector<Point3D>& pts) : points(pts), degenerate(false) {
        build();
    }

    // Checks whether point p lies on the boundary of the convex hull.
    bool on_boundary(const Point3D& p) const {
        // If the point set is lower-dimensional, every point is boundary.
        if(degenerate) {
            return true;
        }

        // Check all current hull faces.
        for(const auto& f: faces) {
            // Ignore removed faces.
            if(!f.alive) {
                continue;
            }

            // If p lies in the plane of a hull face, then because p is inside
            // the hull, p is on the boundary.
            if(signed_volume(
                   points[f.v[0]], points[f.v[1]], points[f.v[2]], p
               ) == 0) {
                return true;
            }
        }

        // Otherwise p is strictly inside the hull.
        return false;
    }

  private:
    // Returns signed volume of face fi with point pi.
    // Positive means point pi is outside face fi.
    coord_t above(int fi, int pi) const {
        const auto& f = faces[fi];
        return signed_volume(
            points[f.v[0]], points[f.v[1]], points[f.v[2]], points[pi]
        );
    }

    // Adds a new triangular face with vertices a, b, c.
    int add_face(int a, int b, int c) {
        // Neighbor indices are initially unknown, hence {-1, -1, -1}.
        faces.push_back({{a, b, c}, {-1, -1, -1}, {}, true});

        // Return the index of the newly added face.
        return (int)faces.size() - 1;
    }

    // Finds directed edge u -> v inside face fi.
    // Returns its local edge index, or -1 if not found.
    int find_edge(int fi, int u, int v) const {
        for(int e = 0; e < 3; e++) {
            if(faces[fi].v[e] == u && faces[fi].v[(e + 1) % 3] == v) {
                return e;
            }
        }
        return -1;
    }

    // Builds the convex hull.
    void build() {
        int n = (int)points.size(); // Number of points.

        // Fewer than 4 points cannot form a 3D hull.
        if(n < 4) {
            degenerate = true;
            return;
        }

        // Indices of the initial tetrahedron vertices.
        int i0 = 0, i1 = -1, i2 = -1, i3 = -1;

        // Find a point different from i0.
        for(int i = 1; i < n; i++) {
            if(!(points[i] == points[i0])) {
                i1 = i;
                break;
            }
        }

        // All points are identical.
        if(i1 < 0) {
            degenerate = true;
            return;
        }

        // Find a point not collinear with i0 and i1.
        for(int i = 1; i < n; i++) {
            if(i == i1) {
                continue;
            }

            // Cross product is zero exactly when vectors are collinear.
            Point3D c = (points[i1] - points[i0]).cross(points[i] - points[i0]);

            if(c.dot(c) > 0) {
                i2 = i;
                break;
            }
        }

        // All points are collinear.
        if(i2 < 0) {
            degenerate = true;
            return;
        }

        // Find a point not coplanar with i0, i1, i2.
        for(int i = 0; i < n; i++) {
            if(i == i0 || i == i1 || i == i2) {
                continue;
            }

            if(signed_volume(points[i0], points[i1], points[i2], points[i]) !=
               0) {
                i3 = i;
                break;
            }
        }

        // All points are coplanar.
        if(i3 < 0) {
            degenerate = true;
            return;
        }

        // Ensure consistent orientation of the tetrahedron.
        if(signed_volume(points[i0], points[i1], points[i2], points[i3]) < 0) {
            swap(i1, i2);
        }

        // Create the 4 faces of the initial tetrahedron.
        int f0 = add_face(i0, i2, i1);
        int f1 = add_face(i1, i2, i3);
        int f2 = add_face(i0, i3, i2);
        int f3 = add_face(i0, i1, i3);

        // Set neighbor relationships between tetrahedron faces.
        faces[f0].nbr = {f2, f1, f3};
        faces[f1].nbr = {f0, f2, f3};
        faces[f2].nbr = {f3, f1, f0};
        faces[f3].nbr = {f0, f1, f2};

        // Assign every non-tetrahedron point to one outside set, if outside.
        for(int p = 0; p < n; p++) {
            if(p == i0 || p == i1 || p == i2 || p == i3) {
                continue;
            }

            // Put point p into the first face whose outside halfspace contains it.
            for(int fi = 0; fi < 4; fi++) {
                if(above(fi, p) > 0) {
                    faces[fi].outside.push_back(p);
                    break;
                }
            }
        }

        // Queue of faces that have outside points and need processing.
        queue<int> q;

        // Initially push tetrahedron faces with outside points.
        for(int fi = 0; fi < 4; fi++) {
            if(!faces[fi].outside.empty()) {
                q.push(fi);
            }
        }

        // Main QuickHull expansion loop.
        while(!q.empty()) {
            int fi = q.front(); // Face to process.
            q.pop();

            // Skip if face was deleted or no longer has outside points.
            if(!faces[fi].alive || faces[fi].outside.empty()) {
                continue;
            }

            // Pick an outside point of this face.
            int apex = faces[fi].outside[0];

            // Distance proxy: signed volume relative to this face.
            coord_t best = above(fi, apex);

            // Find the farthest outside point from this face.
            for(int p: faces[fi].outside) {
                coord_t d = above(fi, p);
                if(d > best) {
                    best = d;
                    apex = p;
                }
            }

            // Faces visible from apex.
            vector<int> visible = {fi};

            // Marks faces already checked in this BFS.
            vector<char> seen(faces.size(), 0);
            seen[fi] = 1;

            // Horizon edges.
            // Each entry stores {u, v, neighboring_face, neighboring_edge_index}.
            vector<array<int, 4>> horizon;

            // BFS over visible faces.
            for(int idx = 0; idx < (int)visible.size(); idx++) {
                int cur = visible[idx];

                // Examine three edges of current face.
                for(int e = 0; e < 3; e++) {
                    int nb = faces[cur].nbr[e]; // Neighbor across this edge.

                    // Ignore missing or already seen neighbors.
                    if(nb < 0 || seen[nb]) {
                        continue;
                    }

                    // If neighbor is also visible from apex, add it.
                    if(above(nb, apex) > 0) {
                        seen[nb] = 1;
                        visible.push_back(nb);
                    } else {
                        // Otherwise this edge is part of the horizon.
                        int u = faces[cur].v[e];
                        int v = faces[cur].v[(e + 1) % 3];

                        // In the neighbor, the same edge is oriented oppositely.
                        int ne = find_edge(nb, v, u);

                        horizon.push_back({u, v, nb, ne});
                    }
                }
            }

            // Points from removed faces that may need redistribution.
            vector<int> orphans;

            // Delete visible faces and collect their outside points.
            for(int vf: visible) {
                for(int p: faces[vf].outside) {
                    if(p != apex) {
                        orphans.push_back(p);
                    }
                }

                faces[vf].outside.clear();
                faces[vf].alive = false;
            }

            // New faces created from apex to every horizon edge.
            vector<int> new_faces;

            // Maps directed edges involving apex to the face containing them.
            map<pair<int, int>, int> apex_edge;

            // Create a new face for each horizon edge.
            for(auto& h: horizon) {
                int u = h[0], v = h[1], nb = h[2], ne = h[3];

                // New triangle connects apex with horizon edge u -> v.
                int nf = add_face(apex, u, v);

                // Across edge u-v, this new face neighbors the old non-visible face.
                faces[nf].nbr[1] = nb;

                // Update old neighbor to point back to the new face.
                faces[nb].nbr[ne] = nf;

                // Store apex-related directed edges for later neighbor linking.
                apex_edge[{apex, u}] = nf;
                apex_edge[{v, apex}] = nf;

                new_faces.push_back(nf);
            }

            // Connect new faces to each other.
            for(int nf: new_faces) {
                int u = faces[nf].v[1];
                int v = faces[nf].v[2];

                // Neighbor across edge apex-u.
                auto it1 = apex_edge.find({u, apex});
                if(it1 != apex_edge.end()) {
                    faces[nf].nbr[0] = it1->second;
                }

                // Neighbor across edge v-apex.
                auto it2 = apex_edge.find({apex, v});
                if(it2 != apex_edge.end()) {
                    faces[nf].nbr[2] = it2->second;
                }
            }

            // Redistribute orphan points among new faces.
            for(int p: orphans) {
                for(int nf: new_faces) {
                    if(above(nf, p) > 0) {
                        faces[nf].outside.push_back(p);
                        break;
                    }
                }
            }

            // Queue new faces that still have outside points.
            for(int nf: new_faces) {
                if(!faces[nf].outside.empty()) {
                    q.push(nf);
                }
            }
        }
    }
};

int n;                  // Number of stars.
vector<string> names;   // Star names.
vector<Point3D> pts;    // Star coordinates.

// Reads input.
void read() {
    string line;

    // Read first line containing n.
    getline(cin, line);
    n = stoi(line);

    // Allocate storage.
    names.assign(n, "");
    pts.assign(n, {});

    // Read star descriptions.
    for(int i = 0; i < n; i++) {
        getline(cin, line);

        // Remove trailing carriage return or spaces.
        while(!line.empty() && (line.back() == '\r' || line.back() == ' ')) {
            line.pop_back();
        }

        // Parse from the end because names may contain spaces.
        auto sp = line.find_last_of(' ');
        coord_t z = stoll(line.substr(sp + 1));
        line.resize(sp);

        sp = line.find_last_of(' ');
        coord_t y = stoll(line.substr(sp + 1));
        line.resize(sp);

        sp = line.find_last_of(' ');
        coord_t x = stoll(line.substr(sp + 1));

        // Remaining prefix is the name.
        names[i] = line.substr(0, sp);

        // Store point.
        pts[i] = {x, y, z};
    }
}

// Solves the problem.
void solve() {
    // Build the 3D convex hull.
    QuickHull3D hull(pts);

    // Names of stars requiring towers.
    vector<string> answer;

    // A tower is needed exactly for boundary points.
    for(int i = 0; i < n; i++) {
        if(hull.on_boundary(pts[i])) {
            answer.push_back(names[i]);
        }
    }

    // Output must be alphabetical.
    sort(answer.begin(), answer.end());

    // Print result.
    cout << answer.size() << '\n';
    for(auto& s: answer) {
        cout << s << '\n';
    }
}

int main() {
    // Fast I/O.
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // There is exactly one test case.
    int T = 1;

    // Process test case.
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 4. Python Solution with Detailed Comments

This Python solution uses a simpler exhaustive method.

Since `n ≤ 100`, we can enumerate all triples of points.  
A plane through three non-collinear points is a hull supporting plane if all points lie on one side of it or on the plane. Every input point lying on such a supporting plane is on the convex hull boundary.

```python
import sys


def sub(a, b):
    """
    Returns vector a - b.
    Points/vectors are represented as tuples (x, y, z).
    """
    return (a[0] - b[0], a[1] - b[1], a[2] - b[2])


def cross(a, b):
    """
    Returns cross product a x b.
    """
    return (
        a[1] * b[2] - a[2] * b[1],
        a[2] * b[0] - a[0] * b[2],
        a[0] * b[1] - a[1] * b[0],
    )


def dot(a, b):
    """
    Returns dot product a . b.
    """
    return a[0] * b[0] + a[1] * b[1] + a[2] * b[2]


def signed_volume(a, b, c, d):
    """
    Returns six times the signed volume of tetrahedron abcd.

    It is positive if d lies on one side of plane abc,
    negative on the other side,
    and zero if a, b, c, d are coplanar.
    """
    return dot(cross(sub(b, a), sub(c, a)), sub(d, a))


def is_zero_vector(v):
    """
    Checks whether a 3D vector is exactly zero.
    """
    return v[0] == 0 and v[1] == 0 and v[2] == 0


def lower_dimensional(points):
    """
    Returns True if all points lie in a space of dimension less than 3:
    a point, a line, or a plane.

    In such cases every input star is considered boundary.
    """
    n = len(points)

    # Fewer than four points cannot form a 3D hull.
    if n < 4:
        return True

    p0 = points[0]

    # Find a point different from p0.
    p1 = None
    for p in points[1:]:
        if p != p0:
            p1 = p
            break

    # All points are identical.
    if p1 is None:
        return True

    # Find a point not collinear with p0 and p1.
    p2 = None
    base = sub(p1, p0)
    for p in points:
        if not is_zero_vector(cross(base, sub(p, p0))):
            p2 = p
            break

    # All points are collinear.
    if p2 is None:
        return True

    # Find a point not coplanar with p0, p1, p2.
    for p in points:
        if signed_volume(p0, p1, p2, p) != 0:
            return False

    # All points are coplanar.
    return True


def main():
    # Read all input lines.
    lines = sys.stdin.read().splitlines()

    # Empty input guard.
    if not lines:
        return

    # First line contains n.
    n = int(lines[0].strip())

    names = []
    points = []

    # Parse each star.
    for i in range(1, n + 1):
        line = lines[i].rstrip("\r")

        # Star names may contain spaces, so parse from the right.
        # The last three space-separated fields are x, y, z.
        name, xs, ys, zs = line.rsplit(" ", 3)

        names.append(name)
        points.append((int(xs), int(ys), int(zs)))

    # If the hull is not truly 3D, all stars are boundary stars.
    if lower_dimensional(points):
        answer = sorted(names)
        print(len(answer))
        print("\n".join(answer))
        return

    # boundary[i] is True if point i lies on some supporting plane.
    boundary = [False] * n

    # Enumerate every triple of points.
    for i in range(n):
        a = points[i]

        for j in range(i + 1, n):
            b = points[j]

            for k in range(j + 1, n):
                c = points[k]

                # Skip collinear triples because they do not define a plane.
                normal = cross(sub(b, a), sub(c, a))
                if is_zero_vector(normal):
                    continue

                has_pos = False
                has_neg = False
                coplanar_indices = []

                # Check all points against the plane through a, b, c.
                for idx, p in enumerate(points):
                    vol = dot(normal, sub(p, a))

                    if vol > 0:
                        has_pos = True
                    elif vol < 0:
                        has_neg = True
                    else:
                        coplanar_indices.append(idx)

                    # If points exist on both sides, this is not a supporting plane.
                    if has_pos and has_neg:
                        break

                # If all points are on one side or on the plane,
                # this plane supports the convex hull.
                if not (has_pos and has_neg):
                    # Every input point lying on that supporting plane is boundary.
                    for idx in coplanar_indices:
                        boundary[idx] = True

    # Collect names of boundary points.
    answer = sorted(names[i] for i in range(n) if boundary[i])

    # Print result.
    print(len(answer))
    print("\n".join(answer))


if __name__ == "__main__":
    main()
```

---

## 5. Compressed Editorial

The laser net is the surface of the convex hull of all stars. Therefore, exactly stars on the convex hull boundary need towers.

Use the signed volume

\[
((b-a) \times (c-a)) \cdot (d-a)
\]

to test the side of point `d` relative to plane `abc`.

The provided C++ solution builds the 3D convex hull using QuickHull:

1. Find four non-coplanar points to form an initial tetrahedron.
2. If impossible, the hull is lower-dimensional, so every star is boundary.
3. Maintain triangular faces, neighbor links, and outside-point lists.
4. Repeatedly choose a face with outside points, pick the farthest outside point, remove all faces visible from it, find the horizon, and create new faces from the horizon to the point.
5. After the hull is built, a point is on the boundary iff it is coplanar with at least one alive hull face.

Finally, sort and print the names of all boundary stars.