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

128. Snake

time limit per test: 0.25 sec.
memory limit per test: 4096 KB


There are N points given by their coordinates on a plane. All coordinates (xi,yi) are integers in a range from -10000 up to 10000 inclusive . It is necessary to construct a broken line satisfying the following conditions:
1. The broken line should be closed.
2. End points of each segment (verteces) of the broken line can only be the given points, and all given points should be used.
3. Each two consecutive segments of the broken line should form a corner of 90 degrees in each vertex point.
4. The sides of the broken line should be parallel to coordinate axes.
5. The broken line should have no self-crossing and self-contact.
6. The broken line should have the minimal length.
You have to either find the length L of the constructed broken line, or determine that it is impossible to construct such a broken line.


Input

First line contains the number N (4 <= N <= 10000) - amount of points. Each of the following N lines contains coordinates of points separated by space xi and yi (1 <= i <= N). Points are given in random order.


Output

First line should contain the length of the broken line L or 0 if there is no solution.


Sample Input

Sample Output

4
0 0
0 3
3 3
3 0
Sample Output

12
Author	: Alex Y. Suslov, Herman "Smash" Narkaytis
Resource	: 5th Southern Subregional Contest. Saratov 2002
Date	: 2002-10-10

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

You are given N (4 ≤ N ≤ 10 000) distinct points with integer coordinates (xi, yi) (−10 000 ≤ xi, yi ≤ 10 000).

You must decide if it is possible to build a *closed* polygonal chain (a cycle) that:

- uses **all** given points, each point exactly once as a vertex;
- has all edges axis-aligned (horizontal or vertical);
- at every vertex, consecutive edges meet at a right angle (no straight-through vertices);
- has no self-intersections and no self-touching;
- has **minimum possible total length** among all such chains.

Output the total length of this chain if it exists, or 0 if it is impossible.

---

2. Key observations
-------------------

1. **Number of vertices must be even**

   - Edges are axis-aligned and at each vertex, direction must change by 90°.
   - That means edges must alternate H–V–H–V–…
   - In a cycle, the number of edges and vertices is equal; for alternating directions to “close up”, the cycle length must be even.
   ⇒ If N is odd → impossible → answer 0.

2. **Edges only between same x or same y**

   - Vertical edge: connects (x, y1) to (x, y2).
   - Horizontal edge: connects (x1, y) to (x2, y).
   So any edge must connect two points with same x or same y.

3. **Even count of points on each x and on each y**

   Each point must have:
   - exactly 1 vertical neighbor (on same x), and
   - exactly 1 horizontal neighbor (on same y).

   So for each distinct x, we must be able to pair points on that x into vertical edges:
   - ⇒ the number of points with that x must be even.
   Similarly, for each distinct y, the number of points with that y must be even.
   If any x or y has an odd count → impossible.

4. **Pairing order along each vertical/horizontal line**

   Fix some x. Suppose points on that x are at y1 < y2 < … < y2k.
   We must pair them up into disjoint vertical segments.

   - If we pair non-neighbors, e.g. (y1, y3) and (y2, y4), those segments either cross or overlap on the same line ⇒ invalid (self-intersection or self-touch).
   - The only way to have non-overlapping, non-touching segments on the same x is to pair consecutive points:
     - (y1, y2), (y3, y4), …, (y2k−1, y2k).

   Same reasoning for fixed y:
   - Sort x1 < x2 < … < x2k
   - Pair horizontally as (x1, x2), (x3, x4), …, (x2k−1, x2k).

   This pairing is:
   - the only pairing without overlaps/touches on that line, and
   - also minimal length for that line (shortest total vertical/horizontal coverage).

5. **Uniqueness and minimality of the whole polygon**

   - For each x and y, the pairing is forced as above.
   - So the entire set of edges (segments) is uniquely determined.
   - Any valid polygon with these constraints must use exactly these segments.
   - Therefore, if a solution exists, this polygon is uniquely determined and automatically minimal.

6. **Graph structure: degree and connectivity**

   - By construction, each point:
     - has exactly 1 incident vertical segment (because its x-group is fully and evenly paired),
     - and 1 incident horizontal segment (y-group paired).
     ⇒ degree = 2 for every vertex.

   - A graph in which each vertex has degree 2 is a disjoint union of cycles.
   - We need exactly **one** cycle covering all vertices: the graph must be connected.

   We can check this with a **Disjoint Set Union (DSU / Union-Find)**:
   - Every time we add an edge between two point indices, we union them.
   - In the end, if all points are in a single DSU component, we have a single cycle; otherwise, multiple cycles or components → impossible.

7. **Intersection / self-touch checks**

   Even if degree = 2 and graph is connected, we still must ensure:
   - no two edges intersect in their interior;
   - no overlapping or touching between non-consecutive edges.

   Because edges are axis-aligned, intersection tests are simple:

   - **Vertical–vertical** (same x):
     - Compare their y-intervals; if they overlap *in open interval* ⇒ invalid.
   - **Horizontal–horizontal** (same y):
     - Compare x-intervals similarly.
   - **Vertical–horizontal**:
     - Suppose vertical at x = xv, y in [y1v, y2v], and horizontal at y = yh, x in [x1h, x2h].
     - They intersect in their interiors if:
       - xv is strictly between x1h and x2h, and
       - yh is strictly between y1v and y2v.

   Any such intersection or touching (beyond regular consecutive-vertex touches, which don’t arise as forbidden cases with the constructed edges) makes the configuration invalid.

   N ≤ 10 000, each point has degree 2, so total edges ≈ N.
   A naive pairwise check is O(N²) ≈ 10⁸ comparisons, which is acceptable in optimized C++.

---

3. Full solution approach
-------------------------

Outline:

1. **Input and trivial parity check**
   - Read N and all points.
   - If N is odd → print 0 and stop.

2. **Group points by x and by y**
   - Maintain:
     - `pnts_on_x[x] = [(y, index)]` list of points having that x.
     - `pnts_on_y[y] = [(x, index)]` list of points having that y.
   - `index` is the position 0..N−1 of the point in the input.

3. **Build candidate vertical segments**
   For each `x`:
   - Sort `pnts_on_x[x]` by y.
   - If the group size is odd → impossible → print 0.
   - Then in steps of 2:
     - Pair `(y1, idx1) = vec[i]` and `(y2, idx2) = vec[i+1]`.
     - If `y1 == y2` → two points with same coordinates (x, y): zero-length segment → treat as invalid → 0.
     - Add vertical segment from (x, y1) to (x, y2) to an `edges` list.
     - Increase `total_length` by `abs(y2 - y1)`.
     - Union `idx1` and `idx2` in the DSU.

4. **Build candidate horizontal segments**
   For each `y`:
   - Sort `pnts_on_y[y]` by x.
   - If group size is odd → impossible → 0.
   - In steps of 2:
     - Pair `(x1, idx1)` and `(x2, idx2)`.
     - If `x1 == x2` → zero-length → invalid → 0.
     - Add horizontal segment ((x1, y), (x2, y)) to `edges`.
     - Increase `total_length` by `abs(x2 - x1)`.
     - Union `idx1` and `idx2` via DSU.

5. **Connectivity check**
   - Let r = root of point 0.
   - Check all i from 1 to N−1:
     - If `find(i) != r` → not one connected component → print 0.

   At this point:
   - Every point has degree 2 (one vertical + one horizontal).
   - All points are connected ⇒ the graph is exactly one cycle.

6. **Intersection / self-contact check**
   - Let `edges` be a list of segments, where each segment is ((x1, y1), (x2, y2)).
   - For each pair i < j:
     - If `segments_intersect(edges[i], edges[j])` is true → print 0.

   The helper `segments_intersect`:
   - Handles three cases:
     1. Both vertical → same x and open interval overlap on y.
     2. Both horizontal → same y and open interval overlap on x.
     3. One vertical and one horizontal → interior intersection with strict inequalities as described above.

   The function uses *strict* inequalities to avoid counting touching at endpoints as valid; any meeting of distinct edges along a line or intersecting midpoints is forbidden.

7. **Output**
   - If all checks passed, print `total_length`.

Complexities:

- Grouping and sorting: O(N log N).
- DSU operations: O(N α(N)) ~ O(N).
- Edge-count ≈ 2N, intersection checks: O(N²).
- Fits within time/memory constraints.

---

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

const int MAXC = (int)1e4 + 42;

class DSU {
  public:
    int n;
    vector<int> par;
    vector<int> sz;

    DSU(int _n = 0) { init(_n); }

    void init(int _n) {
        n = _n;
        par.assign(n + 1, 0);
        sz.assign(n + 1, 0);
        for(int i = 0; i <= n; i++) {
            par[i] = i;
            sz[i] = 1;
        }
    }

    int root(int u) { return par[u] = ((u == par[u]) ? u : root(par[u])); }
    bool connected(int x, int y) { return root(x) == root(y); }

    int unite(int x, int y) {
        x = root(x), y = root(y);
        if(x == y) {
            return x;
        }
        if(sz[x] > sz[y]) {
            swap(x, y);
        }
        par[x] = y;
        sz[y] += sz[x];
        return y;
    }

    vector<vector<int>> components() {
        vector<vector<int>> comp(n + 1);
        for(int i = 0; i <= n; i++) {
            comp[root(i)].push_back(i);
        }
        return comp;
    }
};

int n;
vector<pair<int, int>> pnts;

void read() {
    cin >> n;
    pnts.resize(n);
    cin >> pnts;
}

bool segments_intersect(
    pair<int, int> a1, pair<int, int> a2, pair<int, int> b1, pair<int, int> b2
) {
    auto overlap = [](int a1, int a2, int b1, int b2) {
        return max(min(a1, a2), min(b1, b2)) < min(max(a1, a2), max(b1, b2));
    };

    if(a1.first == a2.first && b1.first == b2.first) {
        return a1.first == b1.first &&
               overlap(a1.second, a2.second, b1.second, b2.second);
    }

    if(a1.second == a2.second && b1.second == b2.second) {
        return a1.second == b1.second &&
               overlap(a1.first, a2.first, b1.first, b2.first);
    }

    if(a1.second == a2.second && b1.first == b2.first) {
        swap(a1, b1);
        swap(a2, b2);
    }

    if(a1.first == a2.first && b1.second == b2.second) {
        return min(a1.second, a2.second) < b1.second &&
               b1.second < max(a1.second, a2.second) &&
               min(b1.first, b2.first) < a1.first &&
               a1.first < max(b1.first, b2.first);
    }

    return false;
}

void solve() {
    /*
     * A few observations pin the answer down to a single candidate polygon:
     *
     * 1) Every vertex turns 90 degrees and the line is closed, so N must be
     *    even.
     *
     * 2) The number of points sharing any fixed X (or any fixed Y) must be
     *    even, since each horizontal/vertical move blocks two points.
     *
     * 3) If the points on a fixed X are Y[1] < ... < Y[2k], the only edges that
     *    avoid intersection/touching are Y[1]-Y[2], Y[3]-Y[4], ...,
     *    Y[2k-1]-Y[2k]; symmetrically for fixed Y.
     *
     * So the edge set is forced. We build it with pnts_on_x / pnts_on_y maps,
     * accumulate the total length, and union the endpoints in a DSU. The shape
     * is valid iff all points end up in one component and no two edges cross
     * (n is small, so the O(E^2) pairwise intersection check passes). Any
     * parity/coincidence violation or failed check prints 0.
     */

    if(n % 2 != 0) {
        cout << 0 << endl;
        return;
    }

    map<int, vector<pair<int, int>>> pnts_on_x, pnts_on_y;
    for(int i = 0; i < n; i++) {
        pnts_on_x[pnts[i].first].push_back({pnts[i].second, i});
        pnts_on_y[pnts[i].second].push_back({pnts[i].first, i});
    }

    DSU dsu(n);
    int64_t total_length = 0;
    vector<pair<pair<int, int>, pair<int, int>>> edges;

    for(auto& it: pnts_on_x) {
        int x = it.first;
        auto& vec = it.second;
        sort(vec.begin(), vec.end());

        if(vec.size() % 2 != 0) {
            cout << 0 << endl;
            return;
        }

        for(int i = 0; i < (int)vec.size(); i += 2) {
            if(vec[i].first == vec[i + 1].first) {
                cout << 0 << endl;
                return;
            }

            int y1 = vec[i].first;
            int y2 = vec[i + 1].first;

            edges.push_back({{x, y1}, {x, y2}});
            total_length += abs(y2 - y1);
            dsu.unite(vec[i].second, vec[i + 1].second);
        }
    }

    for(auto& it: pnts_on_y) {
        int y = it.first;
        auto& vec = it.second;
        sort(vec.begin(), vec.end());

        if(vec.size() % 2 != 0) {
            cout << 0 << endl;
            return;
        }

        for(int i = 0; i < (int)vec.size(); i += 2) {
            if(vec[i].first == vec[i + 1].first) {
                cout << 0 << endl;
                return;
            }

            int x1 = vec[i].first;
            int x2 = vec[i + 1].first;

            edges.push_back({{x1, y}, {x2, y}});
            total_length += abs(x2 - x1);
            dsu.unite(vec[i].second, vec[i + 1].second);
        }
    }

    int root0 = dsu.root(0);
    for(int i = 1; i < n; i++) {
        if(dsu.root(i) != root0) {
            cout << 0 << endl;
            return;
        }
    }

    for(int i = 0; i < (int)edges.size(); i++) {
        for(int j = i + 1; j < (int)edges.size(); j++) {
            if(segments_intersect(
                   edges[i].first, edges[i].second, edges[j].first,
                   edges[j].second
               )) {
                cout << 0 << endl;
                return;
            }
        }
    }

    cout << total_length << endl;
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

5. Python implementation with detailed comments
-----------------------------------------------

```python
import sys
from collections import defaultdict

# We read all input at once for speed
data = sys.stdin.read().strip().split()
it = iter(data)

def read_int():
    return int(next(it))

def main():
    try:
        n = read_int()
    except StopIteration:
        return

    points = []
    for _ in range(n):
        x = read_int()
        y = read_int()
        points.append((x, y))

    # 1. Number of vertices must be even
    if n % 2 == 1:
        print(0)
        return

    # 2. Group points by x and by y
    # For each x -> list of (y, index)
    by_x = defaultdict(list)
    # For each y -> list of (x, index)
    by_y = defaultdict(list)

    for idx, (x, y) in enumerate(points):
        by_x[x].append((y, idx))
        by_y[y].append((x, idx))

    # 3. DSU for connectivity
    parent = list(range(n))
    size = [1] * n

    def find_root(v):
        while parent[v] != v:
            parent[v] = parent[parent[v]]  # path compression
            v = parent[v]
        return v

    def unite(a, b):
        ra = find_root(a)
        rb = find_root(b)
        if ra == rb:
            return
        if size[ra] > size[rb]:
            ra, rb = rb, ra
        parent[ra] = rb
        size[rb] += size[ra]

    edges = []  # list of segments: [((x1,y1),(x2,y2)), ...]
    total_length = 0

    # 4. Build vertical segments
    for x, vec in by_x.items():
        # vec: list of (y, idx)
        vec.sort(key=lambda p: p[0])  # sort by y

        if len(vec) % 2 == 1:
            print(0)
            return

        for i in range(0, len(vec), 2):
            y1, idx1 = vec[i]
            y2, idx2 = vec[i+1]

            if y1 == y2:
                # zero-length segment => two points coincide
                print(0)
                return

            edges.append(((x, y1), (x, y2)))
            total_length += abs(y2 - y1)
            unite(idx1, idx2)

    # 5. Build horizontal segments
    for y, vec in by_y.items():
        # vec: list of (x, idx)
        vec.sort(key=lambda p: p[0])  # sort by x

        if len(vec) % 2 == 1:
            print(0)
            return

        for i in range(0, len(vec), 2):
            x1, idx1 = vec[i]
            x2, idx2 = vec[i+1]

            if x1 == x2:
                print(0)
                return

            edges.append(((x1, y), (x2, y)))
            total_length += abs(x2 - x1)
            unite(idx1, idx2)

    # 6. Connectivity check: all vertices must be in the same DSU component
    root0 = find_root(0)
    for i in range(1, n):
        if find_root(i) != root0:
            print(0)
            return

    # 7. Function to check segment intersections
    def segments_intersect(a1, a2, b1, b2):
        x1a, y1a = a1
        x2a, y2a = a2
        x1b, y1b = b1
        x2b, y2b = b2

        def overlap_strict(a1, a2, b1, b2):
            # strict overlap of 1D segments
            return max(min(a1, a2), min(b1, b2)) < min(max(a1, a2), max(b1, b2))

        a_vertical   = (x1a == x2a)
        b_vertical   = (x1b == x2b)
        a_horizontal = (y1a == y2a)
        b_horizontal = (y1b == y2b)

        # Case 1: both vertical
        if a_vertical and b_vertical:
            if x1a != x1b:
                return False
            return overlap_strict(y1a, y2a, y1b, y2b)

        # Case 2: both horizontal
        if a_horizontal and b_horizontal:
            if y1a != y1b:
                return False
            return overlap_strict(x1a, x2a, x1b, x2b)

        # Normalize: we want A vertical, B horizontal
        if a_horizontal and b_vertical:
            # swap segments so A becomes vertical, B horizontal
            (x1a, y1a, x2a, y2a, x1b, y1b, x2b, y2b) = (
                x1b, y1b, x2b, y2b, x1a, y1a, x2a, y2a
            )
            a_vertical, b_vertical = True, False
            a_horizontal, b_horizontal = False, True

        # Case 3: A is vertical, B is horizontal
        if a_vertical and b_horizontal:
            xv = x1a
            yh = y1b
            return (min(y1a, y2a) < yh < max(y1a, y2a) and
                    min(x1b, x2b) < xv < max(x1b, x2b))

        return False

    # 8. Check all pairs of segments for invalid intersections / overlaps
    m = len(edges)
    for i in range(m):
        a1, a2 = edges[i]
        for j in range(i+1, m):
            b1, b2 = edges[j]
            if segments_intersect(a1, a2, b1, b2):
                print(0)
                return

    # 9. All checks passed
    print(total_length)

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

This Python code follows the same logic as the C++ one, with detailed comments to mirror the reasoning steps.
