题目描述
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; }