<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

290. Defend the Milky Way
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



Year 22204. An alien invasion threatens the Milky Way. It seems like our entire civilization can be demolished. To prevent this, mankind has to build an immensely strong defense system using a brand new weapon invented in the 223rd Century: great laser net. Such net looks like a big laser triangle destroying everything it touches. To set up such laser triangle, you need laser control towers in its vertices. Of course, laser control towers can only be built at star systems, and at most one laser control tower is allowed at one star system.
But this weapon is the most expensive thing in the history of mankind, its cost being proportional to the area of the laser triangle. Laser control towers are way cheaper.
Qc, the greatest mathematician of the time and the commander of human armies, wants to build several laser nets in such a way that no alien can reach a Milky Way star system without being killed by laser. And, of course, he would like the system to be as cheap as possible. So he would like laser triangles to surround the convex hull of all the stars of the Milky Way star system.
If a star is inside or on the border of a laser triangle, you also have to build a laser control tower there to prevent it from being destroyed by laser.

Input
The first line of input contains one integer n (1 <= n <= 100) --- the number of star systems. Next n lines contain descriptions of the star systems: star name (containing characters with ASCII codes from 32 to 255) and its Cartesian coordinates in space (x, y and z). Length of star name doesn't exceed 200, all coordinates are integers not exceeding 10000 by absolute value. Star name and x-coordinate and consecutive coordinates will be separated with a single space.

Output
On the first line of output print the number q of laser control towers to be built. In next q lines output the names of star systems for these towers, ordered alphabetically.

Sample test(s)

Input
Test #1
2
Qc 0 0 0
He 10000 10000 10000

Test #2
7
Altair 2 0 0
Jupiter 0 2 0
Orion 0 0 2
Wx 1 1 0
Statz 0 -5 -5
Unreal -5 0 0
Qc -1 -1 0

Output
Test #1
2
He
Qc

Test #2
6
Altair
Jupiter
Orion
Statz
Unreal
Wx
Author:	Anton Golubev, Petrazavodsk SU
Resource:	Anton Golubev (Hedgehog)'s Contest #2 from Annual Summer Russian Teams Meeting in Petrozavodsk State University
Date:	August 26, 2005

<|response|>
## 1. Abridged problem statement

Given `n ≤ 100` star systems in 3D, each with a name and integer coordinates, determine which stars need laser control towers.

Laser triangles must surround the convex hull of all stars. Any star lying on the surface of this convex hull — including vertices, edges, and faces — needs a tower. Stars strictly inside the 3D convex hull do not.

If all stars are lower-dimensional, for example all lie on a plane or a line, then every star is considered to be on the boundary.

Print the names of all stars needing towers in alphabetical order.

---

## 2. Key observations

### Observation 1: We need convex hull boundary points

A star needs a tower iff it lies on the boundary of the convex hull of all stars.

So the task is:

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

---

### Observation 2: Signed volume tests the side of a point

For 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`.

- `V > 0`: `d` is on one side of plane `abc`.
- `V < 0`: `d` is on the other side.
- `V = 0`: `a, b, c, d` are coplanar.

Coordinates are integers with absolute value at most `10000`, so `int64_t` / Python `int` is safe.

---

### Observation 3: Degenerate inputs make every star a boundary star

If the set of points is not truly 3-dimensional (fewer than 4 points, all equal, all collinear, or all coplanar), the convex hull has no 3D interior, so every star lies on the boundary and needs a tower.

---

## 3. Full solution approach

The C++ solution builds the 3D convex hull explicitly with QuickHull; the Python solution uses a simpler O(n^4) enumeration of supporting planes. Both identify the same set of boundary stars.

### QuickHull (C++)

1. Read all star names and coordinates. Names may contain spaces, so parse each input line from the right: the last three tokens are `x y z`, everything before is the name.

2. Find four non-coplanar input points to form an initial tetrahedron:
   - `i0`: first point;
   - `i1`: first point different from `i0`;
   - `i2`: first point not collinear with `i0, i1`;
   - `i3`: first point not coplanar with `i0, i1, i2`.

   If any of these does not exist, the input is degenerate and every star is on the boundary.

3. Orient the four faces of the tetrahedron so that their normals point outward, and assign every remaining point to the outside list of a face it lies outside of.

4. While some face has outside points:
   - pick the farthest outside point as the `apex`;
   - BFS the connected region of faces visible from `apex`;
   - collect the horizon edges (between visible and non-visible faces);
   - delete the visible faces and replace them by a fan of new triangles from `apex` to each horizon edge;
   - reconnect neighbor pointers and redistribute orphaned outside points to the new faces.

5. After the hull is built, a point `p` is on the boundary iff `signed_volume(a, b, c, p) == 0` for some alive hull face `(a, b, c)`. Because all inputs lie inside or on the hull, lying on a face's supporting plane means lying on the boundary.

### Supporting planes (Python)

Since `n ≤ 100`, enumerate every triple of points. Three non-collinear points define a plane; if all points lie on one side of it or on the plane, it is a supporting plane of the hull, and every input point lying on it is a boundary point.

### Complexity

QuickHull is easily fast enough for `n ≤ 100`. The plane enumeration is `O(n^4)`, also acceptable.

---

## 4. C++ implementation

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

---

## 5. Python implementation

This Python solution uses the simpler exhaustive method: enumerate all triples of points, keep those that define a supporting plane, and mark every input point on such a plane as 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()
```
