## 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. C++ Solution

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

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

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

using coord_t = int64_t;

struct Point3D {
    coord_t x, y, z;

    Point3D(coord_t x = 0, coord_t y = 0, coord_t z = 0) : x(x), y(y), z(z) {}

    Point3D operator+(const Point3D& p) const {
        return {x + p.x, y + p.y, z + p.z};
    }
    Point3D operator-(const Point3D& p) const {
        return {x - p.x, y - p.y, z - p.z};
    }
    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};
    }
    coord_t dot(const Point3D& p) const { return x * p.x + y * p.y + z * p.z; }
    bool operator==(const Point3D& p) const {
        return x == p.x && y == p.y && z == p.z;
    }

    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);
    }
};

class QuickHull3D {
  public:
    struct Face {
        array<int, 3> v;
        array<int, 3> nbr;
        vector<int> outside;
        bool alive;
    };

    vector<Point3D> points;
    vector<Face> faces;
    bool degenerate;

    QuickHull3D(const vector<Point3D>& pts) : points(pts), degenerate(false) {
        build();
    }

    bool on_boundary(const Point3D& p) const {
        if(degenerate) {
            return true;
        }
        for(const auto& f: faces) {
            if(!f.alive) {
                continue;
            }
            if(signed_volume(
                   points[f.v[0]], points[f.v[1]], points[f.v[2]], p
               ) == 0) {
                return true;
            }
        }
        return false;
    }

  private:
    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]
        );
    }

    int add_face(int a, int b, int c) {
        faces.push_back({{a, b, c}, {-1, -1, -1}, {}, true});
        return (int)faces.size() - 1;
    }

    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;
    }

    void build() {
        int n = (int)points.size();
        if(n < 4) {
            degenerate = true;
            return;
        }

        int i0 = 0, i1 = -1, i2 = -1, i3 = -1;
        for(int i = 1; i < n; i++) {
            if(!(points[i] == points[i0])) {
                i1 = i;
                break;
            }
        }
        if(i1 < 0) {
            degenerate = true;
            return;
        }

        for(int i = 1; i < n; i++) {
            if(i == i1) {
                continue;
            }
            Point3D c = (points[i1] - points[i0]).cross(points[i] - points[i0]);
            if(c.dot(c) > 0) {
                i2 = i;
                break;
            }
        }

        if(i2 < 0) {
            degenerate = true;
            return;
        }
        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;
            }
        }

        if(i3 < 0) {
            degenerate = true;
            return;
        }

        if(signed_volume(points[i0], points[i1], points[i2], points[i3]) < 0) {
            swap(i1, i2);
        }

        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);

        faces[f0].nbr = {f2, f1, f3};
        faces[f1].nbr = {f0, f2, f3};
        faces[f2].nbr = {f3, f1, f0};
        faces[f3].nbr = {f0, f1, f2};

        for(int p = 0; p < n; p++) {
            if(p == i0 || p == i1 || p == i2 || p == i3) {
                continue;
            }

            for(int fi = 0; fi < 4; fi++) {
                if(above(fi, p) > 0) {
                    faces[fi].outside.push_back(p);
                    break;
                }
            }
        }

        queue<int> q;
        for(int fi = 0; fi < 4; fi++) {
            if(!faces[fi].outside.empty()) {
                q.push(fi);
            }
        }

        while(!q.empty()) {
            int fi = q.front();
            q.pop();
            if(!faces[fi].alive || faces[fi].outside.empty()) {
                continue;
            }

            int apex = faces[fi].outside[0];
            coord_t best = above(fi, apex);
            for(int p: faces[fi].outside) {
                coord_t d = above(fi, p);
                if(d > best) {
                    best = d;
                    apex = p;
                }
            }

            vector<int> visible = {fi};
            vector<char> seen(faces.size(), 0);
            seen[fi] = 1;
            vector<array<int, 4>> horizon;

            for(int idx = 0; idx < (int)visible.size(); idx++) {
                int cur = visible[idx];
                for(int e = 0; e < 3; e++) {
                    int nb = faces[cur].nbr[e];
                    if(nb < 0 || seen[nb]) {
                        continue;
                    }

                    if(above(nb, apex) > 0) {
                        seen[nb] = 1;
                        visible.push_back(nb);
                    } else {
                        int u = faces[cur].v[e];
                        int v = faces[cur].v[(e + 1) % 3];
                        int ne = find_edge(nb, v, u);
                        horizon.push_back({u, v, nb, ne});
                    }
                }
            }

            vector<int> orphans;
            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;
            }

            vector<int> new_faces;
            map<pair<int, int>, int> apex_edge;
            for(auto& h: horizon) {
                int u = h[0], v = h[1], nb = h[2], ne = h[3];
                int nf = add_face(apex, u, v);
                faces[nf].nbr[1] = nb;
                faces[nb].nbr[ne] = nf;
                apex_edge[{apex, u}] = nf;
                apex_edge[{v, apex}] = nf;
                new_faces.push_back(nf);
            }

            for(int nf: new_faces) {
                int u = faces[nf].v[1];
                int v = faces[nf].v[2];
                auto it1 = apex_edge.find({u, apex});
                if(it1 != apex_edge.end()) {
                    faces[nf].nbr[0] = it1->second;
                }

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

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

            for(int nf: new_faces) {
                if(!faces[nf].outside.empty()) {
                    q.push(nf);
                }
            }
        }
    }
};

int n;
vector<string> names;
vector<Point3D> pts;

void read() {
    string line;
    getline(cin, line);
    n = stoi(line);
    names.assign(n, "");
    pts.assign(n, {});
    for(int i = 0; i < n; i++) {
        getline(cin, line);
        while(!line.empty() && (line.back() == '\r' || line.back() == ' ')) {
            line.pop_back();
        }

        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));
        names[i] = line.substr(0, sp);
        pts[i] = {x, y, z};
    }
}

void solve() {
    // A star needs a laser control tower iff it lies on the boundary of the
    // 3D convex hull of all stars: a star strictly inside the hull is shielded
    // by the laser triangles, while any star on a face, edge or vertex of the
    // hull is touched by some laser triangle and must host its own tower.
    //
    // We build the hull with a 3D Quickhull over integer coordinates. The hull
    // is stored as triangular faces with outward normals and edge-neighbor
    // pointers; the initial tetrahedron uses the first four non-coplanar
    // input points, and at each iteration we pop a face with a non-empty
    // outside set, pick its furthest point, BFS the connected region of
    // visible faces, collect the horizon edges, and replace the visible
    // region by a fan of new triangles incident to the chosen apex. Orphan
    // outside points of the deleted faces are redistributed to the new ones.
    //
    // A point P lies on the boundary iff the signed tetrahedron volume of
    // some hull face together with P vanishes. Coplanar hull faces (when the
    // input is non-generic) are kept by the algorithm; they share a plane,
    // so the same zero-volume test still recognises every coplanar boundary
    // point. Degenerate inputs (fewer than four non-coplanar points) are
    // 0-, 1- or 2-dimensional, so every star is on the boundary.
    //
    // More details can be found in the Quickhull algorithm from Barber, Dobkin,
    // Huhdanpaa, "The Quickhull Algorithm for Convex Hulls", ACM TOMS 22(4),
    // 1996: https://doi.org/10.1145/235815.235821.

    QuickHull3D hull(pts);
    vector<string> answer;
    for(int i = 0; i < n; i++) {
        if(hull.on_boundary(pts[i])) {
            answer.push_back(names[i]);
        }
    }

    sort(answer.begin(), answer.end());
    cout << answer.size() << '\n';
    for(auto& s: answer) {
        cout << s << '\n';
    }
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 4. Python Solution

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.
