首页 > 代码库 > SGU 128.Snake
SGU 128.Snake
时间限制：0.25s
空间限制：4m
题意：
在一个平面坐标中有N个点，现在要你用这N个点构造一个闭合图形，这个图形要满足以下条件：
1.这个图形要是闭合的；
2.图形上的点只能是给定的点，且每个点只能用一次；
3.每个顶点相连的两条边必须互相垂直；
4.每条边都要平行于坐标轴；
5.每条线除了顶点外都不能互相相交；
6.闭合图形的周长要最小；
N-----点的个数
接下来N个点。
如果存在则输出最小长度；否则输出0。
Solution:
重点在所求图形所有的边都是平行于X轴或Y轴，那么要使所有点成直角，只要对所有点先对X轴再对Y轴排序
很容易发现对于在同一条竖线方向和同一条横线方向的点，一定是两个两个点相连。
现在问题是如何判断线段相交的情况
假如现在已经连接完所有竖直方向的边，接着我们连接横向的边，两点为（x1，y，x2，y），
如果存在一条竖直边(a，b1，a，b2) 使得x1<x<x2 且 b1<y<b2 那么这两条边相交
于是可以将排完序的所有的相同的x分为一组，如果x1，和x2所在的组内还有别的组的话即使得x1<x<x2 ，
就将那些组的边取出来，再判断 是否 b1<y<b2 是否满足，最后再判断得的的是否是只有一个闭合曲线，并查集即可。
参考代码：
#include <cstdio>#include <iostream>#include <algorithm>using namespace std;const int INF = 11111;struct node { int x, y, Pxy, Pyx;};int f[INF];node Axy[INF], Ayx[INF];int pos[INF << 2], head[INF];int n, x, y, ans;int Find (int x) { if (f[x] != x) return f[x] = Find (f[x]); return x;}void getT (int a, int b) { f[Find (a)] = Find (b);}int cmpXY (node a, node b) { if (a.x == b.x) return a.y < b.y; return a.x < b.x;}int cmpYX (node a, node b) { if (a.y == b.y) return a.x < b.x; return a.y < b.y;}int make() { if (n & 1 ) return 0; for (int i = 2; i <= n; i += 2) { if (Axy[i - 1].x == Axy[i].x) { getT (i, i - 1); ans += Axy[i].y - Axy[i - 1].y; } else return 0; } for (int i = 2; i <= n; i += 2) { if (Ayx[i - 1].y == Ayx[i].y) { getT (Ayx[i - 1].Pxy, Ayx[i].Pxy); ans += Ayx[i].x - Ayx[i - 1].x; } else return 0; if (pos[Ayx[i - 1].x ] + 1 != pos[Ayx[i].x ]) for (int j = head[pos[Ayx[i - 1].x ] + 1]; j < head[pos[Ayx[i].x ]] - 1; j += 2) if (Axy[j].y < Ayx[i].y && Ayx[i].y < Axy[j + 1].y) return 0; } for (int i = 2; i <= n; i++) if (Find(i) != Find(i-1)) return 0; return ans;}int main() { scanf ("%d", &n); for (int i = 1; i <= n; i++) { scanf ("%d %d", &Axy[i].x, &Axy[i].y); Axy[i].x += INF, Axy[i].y += INF; } sort (Axy + 1, Axy + n + 1, cmpYX); for (int i = 1; i <= n; i++) { Axy[i].Pyx = i; Ayx[i] = Axy[i]; } sort (Axy + 1, Axy + n + 1, cmpXY); int now = -1, t = 0; for (int i = 1; i <= n; i++) { Ayx[Axy[i].Pyx].Pxy = i, f[i] = i; if ( Axy[i].x != now ) { now = Axy[i].x, head[++t] = i; pos[now] = t; } } printf ("%d", make() ); return 0;}