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

int n;
int start_x, start_y;
vector<pair<int, int>> wells;

void read() {
    cin >> n >> start_x >> start_y;
    wells.resize(n);
    for(auto& w: wells) {
        cin >> w;
    }
}

void solve() {
    // Pure implementation. The driver picks two perpendicular directions for
    // phase 1 and the other two for phase 2, so the closed path is bounded by
    // two monotone staircases between the start (treated as origin) and the
    // opposite corner (a, b). The polygon therefore lives in one of the four
    // quadrants relative to the start. For each of the four orientations, we
    // mirror the wells into the first quadrant and look for the smallest
    // staircase polygon containing them.
    //
    // With wells in the first quadrant, set a = max(max_x, 1), b = max(max_y,
    // 1). Describe each staircase by the y-coordinate of its E-step in each
    // column: f_upper(x) for the upper boundary, f_lower(x) for the lower one,
    // both non-decreasing. Wells (xi, yi) require f_upper(xi) >= yi for xi < a
    // (well lies below/on upper path) and f_lower(xi - 1) <= yi for xi > 0
    // (well lies above/on lower path). For the polyline to be simple, the
    // upper path takes its first step N and its last step E (so f_upper(0) >=
    // 1 and f_upper(a - 1) = b), the lower path takes its first step E and
    // its last step N (so f_lower(0) = 0 and f_lower(a - 1) <= b - 1), and
    // for every interior column x in {1, ..., a - 1} the vertical segments
    // do not touch, i.e. f_lower(x) <= f_upper(x - 1) - 1.
    //
    // Greedy is optimal: pick f_upper as the smallest non-decreasing staircase
    // satisfying its lower bounds, then pick f_lower as the largest
    // non-decreasing staircase satisfying its upper bounds (which now include
    // the f_upper-dependent simple-polygon constraint). Increasing f_upper(x -
    // 1) only loosens the constraint on f_lower(x) by the same amount, so it
    // can never decrease the area. Try all four orientations and keep the
    // best; if none works, output -1.

    vector<pair<int, int>> shifted(n);
    for(int i = 0; i < n; i++) {
        shifted[i] = {wells[i].first - start_x, wells[i].second - start_y};
    }

    auto try_orientation = [&](int sx, int sy) -> pair<int64_t, string> {
        vector<pair<int, int>> w(n);
        for(int i = 0; i < n; i++) {
            w[i] = {sx * shifted[i].first, sy * shifted[i].second};
            if(w[i].first < 0 || w[i].second < 0) {
                return {LLONG_MAX, ""};
            }
        }

        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);
        }
        int a = max(max_x, 1);
        int b = max(max_y, 1);

        vector<int> max_y_at_col(a, -1);
        for(auto p: w) {
            if(p.first < a) {
                max_y_at_col[p.first] = max(max_y_at_col[p.first], p.second);
            }
        }

        vector<int> min_y_strictly_right(a, INT_MAX);
        for(auto p: w) {
            for(int xp = 0; xp < p.first && xp < a; xp++) {
                min_y_strictly_right[xp] =
                    min(min_y_strictly_right[xp], p.second);
            }
        }

        vector<int> f_upper(a, 0);
        f_upper[0] = max(1, max_y_at_col[0]);
        for(int x = 1; x < a; x++) {
            int wells_here = max(0, max_y_at_col[x]);
            f_upper[x] = max(f_upper[x - 1], wells_here);
        }
        f_upper[a - 1] = max(f_upper[a - 1], b);
        if(f_upper[a - 1] != b) {
            return {LLONG_MAX, ""};
        }

        vector<int> f_lower(a, 0);
        f_lower[0] = 0;
        for(int x = 1; x < a; x++) {
            int ub = f_upper[x - 1] - 1;
            if(min_y_strictly_right[x] != INT_MAX) {
                ub = min(ub, min_y_strictly_right[x]);
            }
            if(x == a - 1) {
                ub = min(ub, b - 1);
            }
            if(ub < f_lower[x - 1]) {
                return {LLONG_MAX, ""};
            }
            f_lower[x] = ub;
        }

        int64_t area = 0;
        for(int x = 0; x < a; x++) {
            area += f_upper[x] - f_lower[x];
        }
        if(area <= 0) {
            return {LLONG_MAX, ""};
        }

        string path;
        int prev = 0;
        for(int x = 0; x < a; x++) {
            for(int i = 0; i < f_upper[x] - prev; i++) {
                path += 'N';
            }
            path += 'E';
            prev = f_upper[x];
        }

        string lower_path;
        prev = 0;
        for(int x = 0; x < a; x++) {
            for(int i = 0; i < f_lower[x] - prev; i++) {
                lower_path += 'N';
            }
            lower_path += 'E';
            prev = f_lower[x];
        }
        for(int i = 0; i < b - prev; i++) {
            lower_path += 'N';
        }
        for(int i = (int)lower_path.size() - 1; i >= 0; i--) {
            path += (lower_path[i] == 'N' ? 'S' : 'W');
        }

        string result;
        for(char c: path) {
            char d = c;
            if(c == 'N') {
                d = (sy == 1 ? 'N' : 'S');
            } else if(c == 'S') {
                d = (sy == 1 ? 'S' : 'N');
            } else if(c == 'E') {
                d = (sx == 1 ? 'E' : 'W');
            } else if(c == 'W') {
                d = (sx == 1 ? 'W' : 'E');
            }
            result += d;
        }

        return {area, result};
    };

    pair<int64_t, string> best = {LLONG_MAX, ""};
    for(int sx: {1, -1}) {
        for(int sy: {1, -1}) {
            auto r = try_orientation(sx, sy);
            if(r.first < best.first) {
                best = r;
            }
        }
    }

    if(best.first == LLONG_MAX) {
        cout << -1 << '\n';
    } else {
        cout << best.first << '\n' << best.second << '\n';
    }
}

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

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

    return 0;
}
```

---

## 4. Python Solution

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