hexo-blog/source/_posts/oi/snake.md

---

title: Snake tags:

• Constructive Algorithm
• Implementation id: "1582" categories:
• - OI
  • Common Skill date: 2017-10-26 11:05:50 ---

题目描述

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.

题意概述

平面上有$N$个点，现在要用这$N$个点构造一个图形，满足：

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

如果有解，输出最小周长，否则输出$0$。

数据范围：$4 \le N \le 10000$。

算法分析

将所有点以横坐标为第一关键字、纵坐标为第二关键字从小到大排序。

显然，如果有解，那么对于任意整数$x$，横坐标等于$x$的点的个数必须是偶数个，只要将第一个点和第二个点、第三个点和第四个点...相连，再以纵坐标为第一关键字、横坐标为第二关键字从小到大排序，进行一样的操作。最后需要判断是否连通以及是否有相交。

代码

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