<|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: Supporting planes describe hull faces

In 3D, a plane is a supporting plane of the convex hull if all points lie on one side of the plane or on the plane.

If a point lies on a supporting plane, then it lies on the boundary of the convex hull.

For a non-degenerate 3D convex hull, every face lies in such a supporting plane.

---

### Observation 3: We can enumerate all possible face planes

Since `n ≤ 100`, we can enumerate every triple of points.

Three non-collinear points define a plane. For each such plane:

- compute which side every point lies on;
- if all points are on one side or on the plane, this is a supporting plane;
- every input point lying on this plane is a boundary point.

Number of triples is:

\[
\binom{100}{3} = 161700
\]

For every triple we scan at most `100` points, so this is about `16 million` checks, easily fine.

---

### Observation 4: Exact integer geometry is possible

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.

---

## 3. Full solution approach

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 them is the name.

2. Check whether all points are lower-dimensional:

   - fewer than 4 points;
   - all points equal;
   - all points collinear;
   - all points coplanar.

   If so, every star lies on the boundary, so output all names sorted.

3. Otherwise, the convex hull is truly 3D.

4. Initialize `boundary[i] = false` for every point.

5. Enumerate all triples `(i, j, k)`.

   For each triple:

   - If the three points are collinear, skip them.
   - Otherwise they define a plane.
   - Check all points against this plane using signed volume.
   - If there are points on both sides, this plane is not a hull supporting plane.
   - If all points are on one side or on the plane, then this is a supporting plane.
   - Mark all points lying on this plane as boundary points.

6. Collect names of all marked points.

7. Sort the names alphabetically and print them.

### Correctness argument

If a point is marked, then it lies on a plane such that all points are on one side of that plane. Therefore the plane supports the convex hull, and the point is on the hull boundary.

If a point lies on the boundary of a full-dimensional 3D convex hull, it lies on at least one hull face. That face lies in a supporting plane containing at least three non-collinear input vertices. Our enumeration will consider such a triple, recognize the plane as supporting, and mark the point.

For lower-dimensional input, the convex hull has empty 3D interior, so every input point belongs to its boundary.

Therefore the algorithm marks exactly the stars that need towers.

### Complexity

There are `O(n^3)` triples, and for each triple we scan `O(n)` points.

\[
O(n^4)
\]

With `n ≤ 100`, this is easily acceptable.

Memory usage is `O(n)`.

---

## 4. C++ implementation with detailed comments

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

using int64 = long long;

struct Point {
    int64 x, y, z;

    Point() : x(0), y(0), z(0) {}
    Point(int64 x, int64 y, int64 z) : x(x), y(y), z(z) {}

    Point operator-(const Point& other) const {
        return Point(x - other.x, y - other.y, z - other.z);
    }

    bool operator==(const Point& other) const {
        return x == other.x && y == other.y && z == other.z;
    }
};

Point cross_product(const Point& a, const Point& b) {
    return Point(
        a.y * b.z - a.z * b.y,
        a.z * b.x - a.x * b.z,
        a.x * b.y - a.y * b.x
    );
}

int64 dot_product(const Point& a, const Point& b) {
    return a.x * b.x + a.y * b.y + a.z * b.z;
}

bool is_zero_vector(const Point& v) {
    return v.x == 0 && v.y == 0 && v.z == 0;
}

/*
    Six times the signed volume of tetrahedron abcd.

    Equivalently, this tells the side of point d relative to plane abc.
*/
int64 signed_volume(const Point& a, const Point& b, const Point& c, const Point& d) {
    return dot_product(cross_product(b - a, c - a), d - a);
}

/*
    Checks whether all points lie in a space of dimension less than 3:
    point, line, or plane.

    In that case, every input star is considered to be on the boundary.
*/
bool lower_dimensional(const vector<Point>& p) {
    int n = (int)p.size();

    if (n < 4) {
        return true;
    }

    int i0 = 0;
    int i1 = -1;

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

    // All points are identical.
    if (i1 == -1) {
        return true;
    }

    int i2 = -1;

    // Find a point not collinear with p[i0] and p[i1].
    Point base = p[i1] - p[i0];

    for (int i = 0; i < n; i++) {
        Point cr = cross_product(base, p[i] - p[i0]);

        if (!is_zero_vector(cr)) {
            i2 = i;
            break;
        }
    }

    // All points are collinear.
    if (i2 == -1) {
        return true;
    }

    // Check if there exists a point outside the plane p[i0], p[i1], p[i2].
    for (int i = 0; i < n; i++) {
        if (signed_volume(p[i0], p[i1], p[i2], p[i]) != 0) {
            return false;
        }
    }

    // All points are coplanar.
    return true;
}

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

    string line;
    getline(cin, line);

    int n = stoi(line);

    vector<string> names(n);
    vector<Point> points(n);

    for (int i = 0; i < n; i++) {
        getline(cin, line);

        // Remove possible Windows carriage return.
        if (!line.empty() && line.back() == '\r') {
            line.pop_back();
        }

        /*
            Names may contain spaces.

            The last three space-separated tokens are coordinates.
            Everything before them is the star name.
        */
        size_t pos;

        pos = line.find_last_of(' ');
        int64 z = stoll(line.substr(pos + 1));
        line.resize(pos);

        pos = line.find_last_of(' ');
        int64 y = stoll(line.substr(pos + 1));
        line.resize(pos);

        pos = line.find_last_of(' ');
        int64 x = stoll(line.substr(pos + 1));

        string name = line.substr(0, pos);

        names[i] = name;
        points[i] = Point(x, y, z);
    }

    vector<string> answer;

    // Degenerate hull: every point belongs to the boundary.
    if (lower_dimensional(points)) {
        answer = names;
        sort(answer.begin(), answer.end());

        cout << answer.size() << '\n';
        for (const string& s : answer) {
            cout << s << '\n';
        }

        return 0;
    }

    vector<bool> boundary(n, false);

    /*
        Enumerate all triples of points.

        Each non-collinear triple defines a plane.
        If all points are on one side of that plane, it is a supporting plane
        of the convex hull, and all points on it are boundary points.
    */
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                Point normal = cross_product(points[j] - points[i], points[k] - points[i]);

                // Collinear points do not define a plane.
                if (is_zero_vector(normal)) {
                    continue;
                }

                bool has_pos = false;
                bool has_neg = false;

                vector<int> coplanar_points;

                for (int t = 0; t < n; t++) {
                    int64 side = dot_product(normal, points[t] - points[i]);

                    if (side > 0) {
                        has_pos = true;
                    } else if (side < 0) {
                        has_neg = true;
                    } else {
                        coplanar_points.push_back(t);
                    }

                    // Points on both sides means this cannot be a hull face plane.
                    if (has_pos && has_neg) {
                        break;
                    }
                }

                // Supporting plane: all points lie on one side or on the plane.
                if (!(has_pos && has_neg)) {
                    for (int idx : coplanar_points) {
                        boundary[idx] = true;
                    }
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        if (boundary[i]) {
            answer.push_back(names[i]);
        }
    }

    sort(answer.begin(), answer.end());

    cout << answer.size() << '\n';
    for (const string& s : answer) {
        cout << s << '\n';
    }

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys


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


def cross(a, b):
    """
    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):
    """
    Dot product a . b.
    """
    return a[0] * b[0] + a[1] * b[1] + a[2] * b[2]


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


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

    Positive and negative values mean that d lies on different sides
    of plane abc. Zero means coplanar.
    """
    return dot(cross(sub(b, a), sub(c, a)), sub(d, a))


def lower_dimensional(points):
    """
    Returns True if all points lie in a point, a line, or a plane.

    In such cases, the convex hull has no 3D interior, so every star
    is considered to be on the boundary.
    """
    n = len(points)

    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.
    base = sub(p1, p0)
    p2 = None

    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

    # If some point is not coplanar with p0, p1, p2,
    # the set is truly 3-dimensional.
    for p in points:
        if signed_volume(p0, p1, p2, p) != 0:
            return False

    # All points are coplanar.
    return True


def main():
    /*
    Python strings normally assume UTF-8, but the statement allows names
    with byte values up to 255. Therefore we read and output bytes directly.

    Sorting bytes gives lexicographical order by byte value, which matches
    the natural behavior of C++ strings on this problem input.
    */
```

Python does not support block comments with `/* ... */`, so here is the correct complete Python code:

```python
import sys


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


def cross(a, b):
    """
    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):
    """
    Dot product a . b.
    """
    return a[0] * b[0] + a[1] * b[1] + a[2] * b[2]


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


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

    Positive and negative values mean that d lies on different sides
    of plane abc. Zero means coplanar.
    """
    return dot(cross(sub(b, a), sub(c, a)), sub(d, a))


def lower_dimensional(points):
    """
    Returns True if all points lie in a point, a line, or a plane.

    In such cases, the convex hull has no 3D interior, so every star
    is considered to be on the boundary.
    """
    n = len(points)

    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.
    base = sub(p1, p0)
    p2 = None

    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

    # Check whether all points are coplanar.
    for p in points:
        if signed_volume(p0, p1, p2, p) != 0:
            return False

    return True


def main():
    # Read raw bytes because names may contain bytes outside UTF-8.
    data = sys.stdin.buffer.read().splitlines()

    if not data:
        return

    n = int(data[0].strip())

    names = []
    points = []

    for i in range(1, n + 1):
        line = data[i].rstrip(b"\r")

        /*
        This is invalid Python syntax, but conceptually:
        the line format is:
            name x y z

        The name may contain spaces, so split from the right.
        */
```

Again, the above includes explanatory invalid comments. Here is the final valid Python version:

```python
import sys


def sub(a, b):
    return (a[0] - b[0], a[1] - b[1], a[2] - b[2])


def cross(a, 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):
    return a[0] * b[0] + a[1] * b[1] + a[2] * b[2]


def is_zero_vector(v):
    return v[0] == 0 and v[1] == 0 and v[2] == 0


def signed_volume(a, b, c, d):
    return dot(cross(sub(b, a), sub(c, a)), sub(d, a))


def lower_dimensional(points):
    n = len(points)

    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

    if p1 is None:
        return True

    # Find a point not collinear with p0 and p1.
    base = sub(p1, p0)

    p2 = None
    for p in points:
        if not is_zero_vector(cross(base, sub(p, p0))):
            p2 = p
            break

    if p2 is None:
        return True

    # If every point is coplanar with p0, p1, p2, the set is 2D.
    for p in points:
        if signed_volume(p0, p1, p2, p) != 0:
            return False

    return True


def main():
    # Read bytes directly because names may contain non-UTF-8 bytes.
    data = sys.stdin.buffer.read().splitlines()

    if not data:
        return

    n = int(data[0].strip())

    names = []
    points = []

    for i in range(1, n + 1):
        line = data[i].rstrip(b"\r")

        # The last three space-separated fields are x, y, z.
        # Everything before them is the name, which may itself contain spaces.
        name, xs, ys, zs = line.rsplit(b" ", 3)

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

    # Degenerate case: every point is on the boundary.
    if lower_dimensional(points):
        answer = sorted(names)

        output = [str(len(answer)).encode()]
        output.extend(answer)

        sys.stdout.buffer.write(b"\n".join(output))
        if output:
            sys.stdout.buffer.write(b"\n")

        return

    boundary = [False] * n

    # Enumerate all triples 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]

                normal = cross(sub(b, a), sub(c, a))

                # Collinear triples do not define a plane.
                if is_zero_vector(normal):
                    continue

                has_pos = False
                has_neg = False
                coplanar_points = []

                # Test every point against the plane through a, b, c.
                for idx, p in enumerate(points):
                    side = dot(normal, sub(p, a))

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

                    # Plane has points on both sides, so it is not supporting.
                    if has_pos and has_neg:
                        break

                # A supporting plane has all points on one side or on the plane.
                if not (has_pos and has_neg):
                    for idx in coplanar_points:
                        boundary[idx] = True

    answer = sorted(names[i] for i in range(n) if boundary[i])

    output = [str(len(answer)).encode()]
    output.extend(answer)

    sys.stdout.buffer.write(b"\n".join(output))
    if output:
        sys.stdout.buffer.write(b"\n")


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