## 1. Abridged problem statement

Given `n` oil wells on integer grid points and the starting position of a fence-building machine, build a closed non-self-touching polygonal fence along grid edges such that all wells lie inside or on its border.

The machine is defective: its route must consist of two phases. In the first phase it may move only in two perpendicular directions, and after one switch it may move only in the other two opposite directions. For example, it may first use only `N,E`, then only `S,W`.

Find the minimum possible enclosed area and output any valid route producing it, or `-1` if impossible.

Constraints: `1 ≤ n ≤ 400`, coordinates are between `-400` and `400`.

---

## 2. Detailed editorial

### Key geometric observation

The machine route has exactly two monotone parts:

- first part uses two perpendicular directions,
- second part uses the opposite two directions.

For example, suppose the first part uses `N` and `E`. Then the machine starts at some point, moves monotonically northeast to an opposite corner, and then returns monotonically southwest.

So the closed fence is bounded by two monotone staircases between the same two opposite corners.

There are only four possible orientations:

- first phase `N,E`, second phase `S,W`,
- first phase `N,W`, second phase `S,E`,
- first phase `S,E`, second phase `N,W`,
- first phase `S,W`, second phase `N,E`.

Equivalently, relative to the starting point, all wells must lie in one of the four closed quadrants. We can try all four quadrant orientations independently.

For a chosen orientation, mirror coordinates so that all wells should lie in the first quadrant relative to the start.

Let the start become `(0, 0)`. After mirroring, every well must have:

```text
x >= 0, y >= 0
```

If not, this orientation is impossible.

Now we need to build a polygon consisting of:

- an upper monotone path from `(0, 0)` to `(a, b)`,
- a lower monotone path from `(0, 0)` to `(a, b)`,

where the final route is:

```text
upper path forward + lower path backward
```

The area is the vertical distance between the two staircases summed over all columns.

---

### Choosing the bounding rectangle

Let:

```text
a = max(max well x, 1)
b = max(max well y, 1)
```

We need at least width `1` and height `1`, otherwise the polygon would be degenerate.

The opposite corner will be `(a, b)`.

---

### Representing staircases

For each column `x = 0 ... a - 1`:

- `f_upper[x]` is the height of the horizontal eastward step of the upper path in column `x`.
- `f_lower[x]` is the height of the horizontal eastward step of the lower path in column `x`.

Both arrays must be non-decreasing because the paths can only move north and east.

The upper path is built as:

```text
move north to f_upper[0], move east,
move north to f_upper[1], move east,
...
move north to f_upper[a - 1], move east
```

The last value must be `b`, so the upper path ends at `(a, b)`.

The lower path is built similarly, but after the last east move it may need extra north moves to reach `(a, b)`.

---

### Conditions for a valid simple polygon

To avoid degeneracy and self-touching:

1. The upper path must start with a north step:

```text
f_upper[0] >= 1
```

2. The upper path must end with an east step at height `b`:

```text
f_upper[a - 1] = b
```

3. The lower path must start with an east step:

```text
f_lower[0] = 0
```

4. The lower path must end with a north step:

```text
f_lower[a - 1] <= b - 1
```

5. In every interior vertical grid line, the two paths must not touch:

```text
f_lower[x] <= f_upper[x - 1] - 1
```

for `x = 1 ... a - 1`.

---

### Conditions for containing wells

For a well `(xi, yi)`:

- It must be below or on the upper boundary.
- It must be above or on the lower boundary.

Upper condition:

If `xi < a`, then:

```text
f_upper[xi] >= yi
```

Lower condition:

If `xi > 0`, then:

```text
f_lower[xi - 1] <= yi
```

Wells on the left or right border are handled naturally.

---

### Greedy construction of the upper path

We want the smallest possible area.

The upper path contributes positively to area, so we want it as low as possible.

For each column, store the maximum `y` of wells that require the upper path to be at least that high.

Then construct `f_upper` greedily from left to right:

```text
f_upper[0] = max(1, required height in column 0)

for x > 0:
    f_upper[x] = max(f_upper[x - 1], required height in column x)
```

Finally require:

```text
f_upper[a - 1] = b
```

If this is impossible, this orientation fails.

---

### Greedy construction of the lower path

The lower path subtracts from the area, so we want it as high as possible.

However, it must satisfy:

- it is non-decreasing,
- it stays below the upper path,
- it stays below all wells to its right that would otherwise be excluded,
- it leaves room for the final vertical side.

For each `x`, compute the maximum allowed value for `f_lower[x]`.

Then scan left to right:

```text
f_lower[0] = 0

for x = 1 ... a - 1:
    ub = f_upper[x - 1] - 1
    ub = min(ub, minimum y among wells with well_x > x)
    if x == a - 1:
        ub = min(ub, b - 1)

    if ub < f_lower[x - 1]:
        impossible

    f_lower[x] = ub
```

Choosing the largest valid value at every step minimizes the area.

---

### Computing area

The area between two staircase paths is:

```text
area = sum(f_upper[x] - f_lower[x]) for x = 0 ... a - 1
```

If the area is zero or negative, the polygon is invalid.

---

### Constructing the path

Construct the upper path using `N` and `E`.

Construct the lower path also from `(0,0)` to `(a,b)` using `N` and `E`.

Then append the reverse of the lower path, replacing:

```text
N -> S
E -> W
```

This gives a closed route with one switch:

```text
upper path: uses N/E
reverse lower path: uses S/W
```

Finally, if the chosen orientation was mirrored, translate the directions back to the original `N/E/S/W`.

Try all four orientations and output the route with minimum area.

---

## 3. Provided C++ solution with detailed comments

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

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

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

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

// Input operator for vectors, reads all elements of the vector.
template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) { // Iterate by reference over all elements.
        in >> x;      // Read one element.
    }
    return in;        // Return stream for chaining.
};

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

// Number of oil wells.
int n;

// Starting position of the machine.
int start_x, start_y;

// Coordinates of oil wells.
vector<pair<int, int>> wells;

// Reads input.
void read() {
    cin >> n >> start_x >> start_y; // Read number of wells and start point.
    wells.resize(n);                // Allocate space for n wells.

    for(auto& w: wells) {           // Read every well coordinate.
        cin >> w;
    }
}

// Solves the problem.
void solve() {
    /*
        The route consists of two monotone staircase paths.

        For one orientation, after shifting the start to (0,0), all wells must
        lie in the first quadrant. The first half of the path uses only N/E,
        and the second half uses only S/W.

        The polygon is bounded by two monotone paths between (0,0) and (a,b):
        - an upper path,
        - a lower path.

        We try all four mirrored orientations and keep the minimum-area answer.
    */

    // Shift all wells so that the machine start becomes the origin.
    vector<pair<int, int>> shifted(n);

    for(int i = 0; i < n; i++) {
        shifted[i] = {
            wells[i].first - start_x,  // Relative x-coordinate.
            wells[i].second - start_y  // Relative y-coordinate.
        };
    }

    // Tries one orientation.
    // sx = 1 means original east is positive x, sx = -1 mirrors x.
    // sy = 1 means original north is positive y, sy = -1 mirrors y.
    auto try_orientation = [&](int sx, int sy) -> pair<int64_t, string> {
        // Mirrored well coordinates for this orientation.
        vector<pair<int, int>> w(n);

        for(int i = 0; i < n; i++) {
            // Mirror coordinates so that we always solve in the first quadrant.
            w[i] = {
                sx * shifted[i].first,
                sy * shifted[i].second
            };

            // If a well is outside the first quadrant, this orientation cannot work.
            if(w[i].first < 0 || w[i].second < 0) {
                return {LLONG_MAX, ""};
            }
        }

        // Determine the farthest well coordinates.
        int max_x = 0, max_y = 0;

        for(auto p: w) {
            max_x = max(max_x, p.first);
            max_y = max(max_y, p.second);
        }

        // Width and height of the enclosing staircase polygon.
        // Both must be at least 1 to make the polygon non-degenerate.
        int a = max(max_x, 1);
        int b = max(max_y, 1);

        // max_y_at_col[x] stores the highest well at exact x-coordinate x.
        // It is used to force the upper path to be high enough.
        vector<int> max_y_at_col(a, -1);

        for(auto p: w) {
            // Wells at x == a lie on the right boundary and do not impose
            // an upper horizontal-step constraint.
            if(p.first < a) {
                max_y_at_col[p.first] = max(max_y_at_col[p.first], p.second);
            }
        }

        // min_y_strictly_right[x] stores the minimum y among wells with x-coordinate > x.
        // The lower path at column x must not rise above such wells.
        vector<int> min_y_strictly_right(a, INT_MAX);

        for(auto p: w) {
            // For every column xp strictly to the left of the well,
            // this well limits how high the lower path may be.
            for(int xp = 0; xp < p.first && xp < a; xp++) {
                min_y_strictly_right[xp] =
                    min(min_y_strictly_right[xp], p.second);
            }
        }

        // Construct the lowest possible upper path.
        vector<int> f_upper(a, 0);

        // The upper path must start with a north step,
        // so f_upper[0] must be at least 1.
        // It also must be high enough to contain wells in column 0.
        f_upper[0] = max(1, max_y_at_col[0]);

        // Continue left to right.
        for(int x = 1; x < a; x++) {
            // Wells in this column require this height.
            int wells_here = max(0, max_y_at_col[x]);

            // The staircase must be non-decreasing.
            f_upper[x] = max(f_upper[x - 1], wells_here);
        }

        // The last horizontal step of the upper path must be at height b,
        // so that the upper path ends at (a,b).
        f_upper[a - 1] = max(f_upper[a - 1], b);

        // If f_upper[a - 1] exceeded b, ending at height b would be impossible.
        if(f_upper[a - 1] != b) {
            return {LLONG_MAX, ""};
        }

        // Construct the highest possible lower path.
        vector<int> f_lower(a, 0);

        // The lower path must start with an east step from (0,0).
        f_lower[0] = 0;

        // Fill remaining columns.
        for(int x = 1; x < a; x++) {
            // To avoid touching/crossing the upper path at vertical line x,
            // lower[x] must be at most upper[x-1] - 1.
            int ub = f_upper[x - 1] - 1;

            // If there are wells strictly to the right of x,
            // the lower path here cannot be above their y-coordinate.
            if(min_y_strictly_right[x] != INT_MAX) {
                ub = min(ub, min_y_strictly_right[x]);
            }

            // At the last column, the lower path must leave room for
            // a final north step to reach height b.
            if(x == a - 1) {
                ub = min(ub, b - 1);
            }

            // Since f_lower must be non-decreasing, this upper bound must
            // be at least the previous value.
            if(ub < f_lower[x - 1]) {
                return {LLONG_MAX, ""};
            }

            // Greedily choose the largest possible height to minimize area.
            f_lower[x] = ub;
        }

        // Compute area between upper and lower staircases.
        int64_t area = 0;

        for(int x = 0; x < a; x++) {
            area += f_upper[x] - f_lower[x];
        }

        // Area must be positive.
        if(area <= 0) {
            return {LLONG_MAX, ""};
        }

        // Build the actual path string in normalized coordinates.
        string path;

        // prev is current y-coordinate while constructing upper path.
        int prev = 0;

        // Construct upper path from (0,0) to (a,b).
        for(int x = 0; x < a; x++) {
            // Move north until reaching f_upper[x].
            for(int i = 0; i < f_upper[x] - prev; i++) {
                path += 'N';
            }

            // Move one step east in this column.
            path += 'E';

            // Update current height.
            prev = f_upper[x];
        }

        // Build the lower path separately from (0,0) to (a,b).
        string lower_path;

        // Current y-coordinate for lower path.
        prev = 0;

        for(int x = 0; x < a; x++) {
            // Move north until reaching f_lower[x].
            for(int i = 0; i < f_lower[x] - prev; i++) {
                lower_path += 'N';
            }

            // Move east one step.
            lower_path += 'E';

            // Update current height.
            prev = f_lower[x];
        }

        // Finish lower path by moving north to height b.
        for(int i = 0; i < b - prev; i++) {
            lower_path += 'N';
        }

        // Append the reverse of lower_path to path.
        // Reversing N/E gives S/W.
        for(int i = (int)lower_path.size() - 1; i >= 0; i--) {
            path += (lower_path[i] == 'N' ? 'S' : 'W');
        }

        // Convert normalized directions back to original orientation.
        string result;

        for(char c: path) {
            char d = c;

            // Vertical directions may be mirrored.
            if(c == 'N') {
                d = (sy == 1 ? 'N' : 'S');
            } else if(c == 'S') {
                d = (sy == 1 ? 'S' : 'N');
            }

            // Horizontal directions may be mirrored.
            else if(c == 'E') {
                d = (sx == 1 ? 'E' : 'W');
            } else if(c == 'W') {
                d = (sx == 1 ? 'W' : 'E');
            }

            // Append converted direction.
            result += d;
        }

        // Return area and constructed route.
        return {area, result};
    };

    // Best answer among all orientations.
    pair<int64_t, string> best = {LLONG_MAX, ""};

    // Try all four quadrant orientations.
    for(int sx: {1, -1}) {
        for(int sy: {1, -1}) {
            auto r = try_orientation(sx, sy);

            // Keep smaller area.
            if(r.first < best.first) {
                best = r;
            }
        }
    }

    // If all orientations failed, print -1.
    if(best.first == LLONG_MAX) {
        cout << -1 << '\n';
    } else {
        // Otherwise print minimum area and a valid path.
        cout << best.first << '\n' << best.second << '\n';
    }
}

// Program entry point.
int main() {
    // Fast input/output.
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

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

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

    return 0;
}
```

---

## 4. Python solution with detailed comments

```python
import sys


def solve():
    # Read all integers from input.
    data = list(map(int, sys.stdin.read().split()))

    # First three integers are n and starting coordinates.
    n = data[0]
    start_x = data[1]
    start_y = data[2]

    # Read well coordinates.
    wells = []
    idx = 3
    for _ in range(n):
        x = data[idx]
        y = data[idx + 1]
        idx += 2
        wells.append((x, y))

    # Shift wells so that the machine start becomes (0, 0).
    shifted = [(x - start_x, y - start_y) for x, y in wells]

    # Large value representing impossible answer.
    INF = 10**30

    def try_orientation(sx, sy):
        """
        Try one orientation.

        sx = 1 means positive x is east.
        sx = -1 means positive x is west.

        sy = 1 means positive y is north.
        sy = -1 means positive y is south.

        After multiplying by sx and sy, we solve only the first-quadrant case.
        """

        # Mirrored coordinates.
        w = []

        for x, y in shifted:
            nx = sx * x
            ny = sy * y

            # In this orientation, all wells must be in the first quadrant.
            if nx < 0 or ny < 0:
                return INF, ""

            w.append((nx, ny))

        # Determine farthest well coordinates.
        max_x = max((x for x, _ in w), default=0)
        max_y = max((y for _, y in w), default=0)

        # Opposite corner of the staircase polygon.
        # Width and height must be at least 1.
        a = max(max_x, 1)
        b = max(max_y, 1)

        # max_y_at_col[x] is the highest well exactly in column x.
        # This constrains the upper path.
        max_y_at_col = [-1] * a

        for x, y in w:
            # Wells at x == a lie on the right boundary.
            if x < a:
                if y > max_y_at_col[x]:
                    max_y_at_col[x] = y

        # min_y_strictly_right[x] is the minimum y among wells with well_x > x.
        # This constrains how high the lower path may be.
        BIG = 10**9
        min_y_strictly_right = [BIG] * a

        for x, y in w:
            # This well restricts every lower-path column strictly to its left.
            limit = min(x, a)
            for xp in range(limit):
                if y < min_y_strictly_right[xp]:
                    min_y_strictly_right[xp] = y

        # Build the lowest valid upper path.
        f_upper = [0] * a

        # Upper path must begin with a north step and cover wells in column 0.
        f_upper[0] = max(1, max_y_at_col[0])

        for x in range(1, a):
            # Required height due to wells in this column.
            wells_here = max(0, max_y_at_col[x])

            # Staircase height cannot decrease.
            f_upper[x] = max(f_upper[x - 1], wells_here)

        # Last upper horizontal step must be at height b.
        f_upper[a - 1] = max(f_upper[a - 1], b)

        # If it became greater than b, impossible.
        if f_upper[a - 1] != b:
            return INF, ""

        # Build the highest valid lower path.
        f_lower = [0] * a

        # Lower path starts with an east move from height 0.
        f_lower[0] = 0

        for x in range(1, a):
            # To avoid touching upper path.
            ub = f_upper[x - 1] - 1

            # To keep wells to the right above or on lower path.
            if min_y_strictly_right[x] != BIG:
                ub = min(ub, min_y_strictly_right[x])

            # Last column must leave space for final north move.
            if x == a - 1:
                ub = min(ub, b - 1)

            # Lower path must be non-decreasing.
            if ub < f_lower[x - 1]:
                return INF, ""

            # Choose highest possible value to minimize area.
            f_lower[x] = ub

        # Compute polygon area.
        area = 0
        for x in range(a):
            area += f_upper[x] - f_lower[x]

        # Non-degenerate polygon must have positive area.
        if area <= 0:
            return INF, ""

        # Construct upper path in normalized N/E coordinates.
        path = []
        prev = 0

        for x in range(a):
            # Move north up to f_upper[x].
            path.extend("N" for _ in range(f_upper[x] - prev))

            # Move east one column.
            path.append("E")

            # Update current height.
            prev = f_upper[x]

        # Construct lower path from (0,0) to (a,b), also using N/E.
        lower_path = []
        prev = 0

        for x in range(a):
            # Move north up to f_lower[x].
            lower_path.extend("N" for _ in range(f_lower[x] - prev))

            # Move east one column.
            lower_path.append("E")

            # Update current height.
            prev = f_lower[x]

        # Finish lower path by moving north to height b.
        lower_path.extend("N" for _ in range(b - prev))

        # Return along the reverse of lower path.
        # Reverse N -> S and E -> W.
        for c in reversed(lower_path):
            if c == "N":
                path.append("S")
            else:
                path.append("W")

        # Convert directions back from normalized orientation.
        result = []

        for c in path:
            if c == "N":
                result.append("N" if sy == 1 else "S")
            elif c == "S":
                result.append("S" if sy == 1 else "N")
            elif c == "E":
                result.append("E" if sx == 1 else "W")
            else:  # c == "W"
                result.append("W" if sx == 1 else "E")

        return area, "".join(result)

    # Try all four orientations.
    best_area = INF
    best_path = ""

    for sx in (1, -1):
        for sy in (1, -1):
            area, path = try_orientation(sx, sy)

            if area < best_area:
                best_area = area
                best_path = path

    # Output answer.
    if best_area == INF:
        print(-1)
    else:
        print(best_area)
        print(best_path)


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

---

## 5. Compressed editorial

The route always consists of two monotone staircases between the start and an opposite corner. Try all four orientations by mirroring coordinates so the first phase is always `N/E` and the second phase is `S/W`. If any well is outside the first quadrant in that orientation, it is impossible.

Let the opposite corner be `(a,b)`, where:

```text
a = max(max_x, 1)
b = max(max_y, 1)
```

Represent the two staircases by arrays:

```text
upper[x] = height of the upper horizontal step in column x
lower[x] = height of the lower horizontal step in column x
```

for `x = 0 ... a-1`.

Build `upper` as low as possible while non-decreasing and covering wells:

```text
upper[0] >= 1
upper[x] >= highest well y at column x
upper[a-1] = b
```

Build `lower` as high as possible while non-decreasing, staying below `upper`, and not excluding wells:

```text
lower[0] = 0
lower[x] <= upper[x-1] - 1
lower[x] <= y of every well strictly to the right of x
lower[a-1] <= b - 1
```

If construction fails, discard the orientation.

Area is:

```text
sum(upper[x] - lower[x])
```

Construct the route as:

```text
upper path forward + reverse(lower path)
```

Then convert mirrored directions back. Pick the orientation with minimum area, or print `-1` if none works.