POJ3555//POJ3130//POJ1474-求解多边形内核

发布时间:2016-12-7 0:02:40 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"POJ3555//POJ3130//POJ1474-求解多边形内核",主要涉及到POJ3555//POJ3130//POJ1474-求解多边形内核方面的内容,对于POJ3555//POJ3130//POJ1474-求解多边形内核感兴趣的同学可以参考一下。

POJ3555: 题目:题目链接   题意:就是判断一个多边形是不是有核,(多边形内核);(学习.....)   分析:就是每次枚举一条线段,用这条线段去切割原来的多边形,判断最后剩余的点数。如果没有了的话,那么就没有核的存在了,反之则有   一个我认为比较清楚的代码:   #include <iostream> #include <cstdio> #include <string> #include <string.h> #include <map> #include <vector> #include <cstdlib> #include <algorithm> #include <cmath> #include <queue> #include <set> #include <stack> #include <functional> #include <fstream> #include <sstream> #include <iomanip> #include <numeric> #include <cassert> #include <bitset> #include <stack> #include <ctime> #include <list> #define INF 0x7fffffff #define max3(a,b,c) (max(a,b)>c?max(a,b):c) #define min3(a,b,c) (min(a,b)<c?min(a,b):c) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; #define exp 1e-10 struct node { double x; double y; }; node point[105];//记录最开始的多边形 node q[105]; //临时保存新切割的多边形 node p[105]; //保存新切割出的多边形 int n,m;//n的原先的点数,m是新切割出的多边形的点数 double a,b,c; void getline(node x,node y) //获取直线ax+by+c==0 { a=y.y-x.y; b=x.x-y.x; c=y.x*x.y-x.x*y.y; } node intersect(node x,node y) //获取直线ax+by+c==0 和点x和y所连直线的交点 { double u=fabs(a*x.x+b*x.y+c); double v=fabs(a*y.x+b*y.y+c); node ans; ans.x=(x.x*v+y.x*u)/(u+v); ans.y=(x.y*v+y.y*u)/(u+v); return ans; } void cut() //用直线ax+by+c==0切割多边形 { int cutm=0,i; for(i=1; i<=m; i++) { if(a*p[i].x + b*p[i].y+c>=0) //题目是顺时钟给出点的 { //所以一个点在直线右边的话,那么带入值就会大于等于0 q[++cutm]=p[i]; //说明这个点还在切割后的多边形内,将其保留 } else { if(a*p[i-1].x+b*p[i-1].y+c>0) //该点不在多边形内,但是它和它相邻的点构成直线与 { //ax+by+c==0所构成的交点可能在新切割出的多边形内, q[++cutm]=intersect(p[i-1],p[i]); //所以保留交点 } if(a*p[i+1].x+b*p[i+1].y+c>0) { q[++cutm]=intersect(p[i+1],p[i]); } } } for(i = 1; i <= cutm; i++) p[i] = q[i]; p[cutm+1] = q[1]; p[0] = q[cutm]; m = cutm; } void solve() { int i; for(i = 1; i <= n; i++) p[i] = point[i]; point[n+1] = point[1]; p[n+1]=p[1]; p[0]=p[n]; m = n; for(i=1; i<=n; i++) { getline(point[i], point[i+1]); //根据point[i]和point[i+1]确定直线ax+by+c==0 cut(); //用直线ax+by+c==0切割多边形 } } int main() { int cas,i; scanf("%d",&cas); while(cas--) { scanf("%d",&n); for(i=1; i<=n; i++) scanf("%lf%lf",&point[i].x,&point[i].y); solve(); if(m==0) printf("NO\n"); else printf("YES\n"); } return 0; }   POJ 3130 题目:题目链接   题意:和3555是一样的不过不知道这个精度是怎么影响的要用1e-8的,其它的都一样:   代码:   #include <iostream> #include <cstdio> #include <string> #include <string.h> #include <map> #include <vector> #include <cstdlib> #include <algorithm> #include <cmath> #include <queue> #include <set> #include <stack> #include <functional> #include <fstream> #include <sstream> #include <iomanip> #include <numeric> #include <cassert> #include <bitset> #include <stack> #include <ctime> #include <list> #define INF 0x7fffffff #define max3(a,b,c) (max(a,b)>c?max(a,b):c) #define min3(a,b,c) (min(a,b)<c?min(a,b):c) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; #define exp 1e-8 struct node { double x; double y; }; node point[105];//记录最开始的多边形 node q[105]; //临时保存新切割的多边形 node p[105]; //保存新切割出的多边形 int n,m;//n的原先的点数,m是新切割出的多边形的点数 double a,b,c; void getline(node x,node y) //获取直线ax+by+c==0 { a=y.y-x.y; b=x.x-y.x; c=y.x*x.y-x.x*y.y; } node intersect(node x, node y) //获取直线ax+by+c==0 和点x和y所连直线的交点 { double u = fabs(a*x.x + b*x.y+c); double v = fabs(a*y.x + b*y.y+c); node ans; ans.x = (x.x*v+y.x*u)/(u+v); ans.y = (x.y*v+y.y*u)/(u+v); return ans; } void cut() //用直线ax+by+c==0切割多边形 { int cutm=0,i; for(i=1; i<=m; i++) { if(a*p[i].x + b*p[i].y+c <=0) //题目是逆时钟给出点的所以一个点在直线右边的话,那么带入值就会大于等于0 { q[++cutm]=p[i]; //说明这个点还在切割后的多边形内,将其保留 } else { if(a*p[i-1].x+b*p[i-1].y+c <= 0) //该点不在多边形内,但是它和它相邻的点构成直线与ax+by+c==0所构成的交点可能在新切割出的多边形内, { q[++cutm]=intersect(p[i-1], p[i]); //所以保留交点 } if(a*p[i+1].x+b*p[i+1].y+c <= 0) { q[++cutm]=intersect(p[i+1],p[i]); } } } for(i = 1; i <= cutm; i++) p[i] = q[i]; p[cutm+1] = q[1]; p[0] = q[cutm]; m = cutm; } void solve() { int i; for(i = 1; i <= n; i++) p[i] = point[i]; point[n+1] = point[1]; p[n+1]=p[1]; p[0]=p[n]; m = n; for(i=1; i<=n; i++) { getline(point[i], point[i+1]); //根据point[i]和point[i+1]确定直线ax+by+c==0 cut(); //用直线ax+by+c==0切割多边形 } } int main() { int i; while(scanf("%d",&n) && n) { for(i=1; i<=n; i++) scanf("%lf%lf",&point[i].x, &point[i].y); solve(); if(m == 0) printf("0\n"); else printf("1\n"); } return 0; }  POJ1474: 题目:题目链接   分析:也是一个求多边形内核的问题   代码:   #include <iostream> #include <cstdio> #include <string> #include <string.h> #include <map> #include <vector> #include <cstdlib> #include <algorithm> #include <cmath> #include <queue> #include <set> #include <stack> #include <functional> #include <fstream> #include <sstream> #include <iomanip> #include <numeric> #include <cassert> #include <bitset> #include <stack> #include <ctime> #include <list> #define INF 0x7fffffff #define max3(a,b,c) (max(a,b)>c?max(a,b):c) #define min3(a,b,c) (min(a,b)<c?min(a,b):c) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; #define exp 1e-8 struct node { double x; double y; }; node point[105];//记录最开始的多边形 node q[105]; //临时保存新切割的多边形 node p[105]; //保存新切割出的多边形 int n,m;//n的原先的点数,m是新切割出的多边形的点数 double a,b,c; void getline(node x,node y) //获取直线ax+by+c==0 { a=y.y-x.y; b=x.x-y.x; c=y.x*x.y-x.x*y.y; } node intersect(node x, node y) //获取直线ax+by+c==0 和点x和y所连直线的交点 { double u = fabs(a*x.x + b*x.y+c); double v = fabs(a*y.x + b*y.y+c); node ans; ans.x = (x.x*v+y.x*u)/(u+v); ans.y = (x.y*v+y.y*u)/(u+v); return ans; } void cut() //用直线ax+by+c==0切割多边形 { int cutm=0,i; for(i=1; i<=m; i++) { if(a*p[i].x + b*p[i].y+c >=0) //题目是顺时钟给出点的所以一个点在直线右边的话,那么带入值就会大于等于0 { q[++cutm]=p[i]; //说明这个点还在切割后的多边形内,将其保留 } else { if(a*p[i-1].x+b*p[i-1].y+c > 0) //该点不在多边形内,但是它和它相邻的点构成直线与ax+by+c==0所构成的交点可能在新切割出的多边形内, { q[++cutm]=intersect(p[i-1], p[i]); //所以保留交点 } if(a*p[i+1].x+b*p[i+1].y+c > 0) { q[++cutm]=intersect(p[i+1],p[i]); } } } for(i = 1; i <= cutm; i++) p[i] = q[i]; p[cutm+1] = q[1]; p[0] = q[cutm]; m = cutm; } void solve() { int i; for(i = 1; i <= n; i++) p[i] = point[i]; point[n+1] = point[1]; p[n+1]=p[1]; p[0]=p[n]; m = n; for(i=1; i<=n; i++) { getline(point[i], point[i+1]); //根据point[i]和point[i+1]确定直线ax+by+c==0 cut(); //用直线ax+by+c==0切割多边形 } } int main() { int i; int cnt = 0; while(scanf("%d",&n) && n) { cnt++; for(i=1; i<=n; i++) scanf("%lf%lf",&point[i].x, &point[i].y); solve(); printf("Floor #%d\n", cnt); if(m == 0) printf("Surveillance is impossible.\n\n"); else printf("Surveillance is possible.\n\n"); } return 0; }    

上一篇:数据结构学习笔记
下一篇:js,java如何将秒转换成几时几分几秒

相关文章

相关评论