1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94
| #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; }
|