SGU 128.Snake
2024-08-26 09:53:14
时间限制: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;
}
最新文章
- MyEclipse生成注册码
- 移动到web整理
- block,inline和inlinke-block细节对比
- monodb C#接口封装
- UpdatePanel的使用
- tyvj100题留念
- FPGA中如何实现除法?
- html5 canvas图片马赛克
- 使用Visual Leak Detector检测内存泄漏[转]
- lucene学习笔记:二,Lucene的框架
- java 枚举 类 enum
- Python基础【第十一篇】文件操作(file()、open()方法和fileinput模块)
- OC——NSString的常用方法
- ffdshow 源代码分析 3: 位图覆盖滤镜(设置部分Settings)
- python生产环境部署
- JDK 8 之 Stream sorted() 示例
- 2018-2019-2 网络对抗技术 20165304 Exp6 信息搜集与漏洞扫描
- java.lang.NoClassDefFoundError: javax/annotation/Priority
- cocos2dx学习之路
- stingray中modal window
热门文章
- Python IDLE 清屏工具
- Java基础(三)
- intellij idea 2016版破解方法
- 4种字符串匹配算法:KMP(下)
- 实现自己的脚本语言ngscript之一:词法分析
- Call-time pass-by-reference has been deprecated
- JAVA 线程状态以及synchronized,wait,sleep,yield,notify,notifyAll
- C# 字符串常用操作 分类: C# 2014-08-22 15:07 238人阅读 评论(0) 收藏
- (转)Google Fonts 的介绍与使用
- Web App和Native App 谁将是未来