# Snake

## 题目描述

There are $N$ points given by their coordinates on a plane. All coordinates $(x_i, y_i)$ are integers in a range from $-10000$ up to $10000$ inclusive . It is necessary to construct a broken line satisfying the following conditions:

• The broken line should be closed.
• End points of each segment (verteces) of the broken line can only be the given points, and all given points should be used.
• Each two consecutive segments of the broken line should form a corner of 90 degrees in each vertex point.
• The sides of the broken line should be parallel to coordinate axes.
• The broken line should have no self-crossing and self-contact.
• 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.

## 题意概述

• 这个图形是闭合的；
• 每条边的端点必须是给定的点，且每个给定的点必须被用到；
• 每个点连接的两条边必须互相垂直；
• 每条边必须平行于坐标轴；
• 任意两条边除了顶点外不能相交；
• 这个图形的周长最小。

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
inline void write(char c) { putchar(c); }
inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Point { int x, y, id; };

bool cmpx(Point a, Point b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }
bool cmpy(Point a, Point b) { return a.y == b.y ? a.x < b.x : a.y < b.y; }
bool cmpi(Point a, Point b) { return a.id < b.id; }

struct Line { Point a, b; };

struct Solver {
private:
static const int N = 10010;
int n, top, fa[N];
Point point[N];
Line line[N];
void input() {
io > n;
for (int i = 1; i <= n; ++ i) io > point[i].x > point[i].y, point[i].id = i;
}
bool inter(Line p, Line q) {
if (p.a.x == p.b.x && q.a.x == q.b.x) {
if (p.a.y > q.a.y) swap(p, q);
if (p.a.x != q.a.x) return false;
else return p.b.y > q.a.y;
} else if (p.a.y == p.b.y && q.a.y == q.b.y) {
if (p.a.x > q.a.x) swap(p, q);
if (p.a.y != q.a.y) return false;
else return p.b.x > q.a.x;
} else {
if (p.a.x != p.b.x) swap(p, q);
return p.a.y < q.a.y && q.a.y < p.b.y && q.a.x < p.a.x && p.a.x < q.b.x;
}
}
int get_fa(int t) { return t == fa[t] ? t : fa[t] = get_fa(fa[t]); }
void process() {
int l = 0, r = 0, cnt = n - 1;
sort(point + 1, point + n + 1, cmpx);
for (int i = 1; i <= n; i = r) {
l = i, r = i + 1;
while (r <= n && point[r].x == point[l].x) ++ r;
if (r - l & 1) { io < 0 < '\n'; return; }
for (int j = l; j < r; j += 2) line[++ top] = (Line) { point[j], point[j + 1] };
}
sort(point + 1, point + n + 1, cmpy);
for (int i = 1; i <= n; i = r) {
l = i, r = i + 1;
while (r <= n && point[r].y == point[l].y) ++ r;
if (r - l & 1) { io < 0 < '\n'; return; }
for (int j = l; j < r; j += 2) line[++ top] = (Line) { point[j], point[j + 1] };
}
sort(point + 1, point + n + 1, cmpi);
for (int i = 1; i <= top; ++ i)
if (line[i].a.x > line[i].b.x || line[i].a.y > line[i].b.y) swap(line[i].a, line[i].b);
for (int i = 1; i < top; ++ i)
for (int j = i + 1; j <= top; ++ j)
if (inter(line[i], line[j])) { io < 0 < '\n'; return; }
for (int i = 1; i <= n; ++ i) fa[i] = i;
for (int i = 1; i <= top; ++ i) {
int p = get_fa(line[i].a.id), q = get_fa(line[i].b.id);
if (p != q) fa[p] = q, -- cnt;
}
if (cnt) { io < 0 < '\n'; return; }
int ans = 0;
for (int i = 1; i <= top; ++ i) ans += line[i].b.x - line[i].a.x + line[i].b.y - line[i].a.y;
io < ans < '\n';
}

public:
void solve() { input(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}


418 I'm a teapot