好贷网好贷款

Shape of HDU(hdu2108,叉乘判断多边凹凸性)

发布时间:2016-12-4 22:21:25 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Shape of HDU(hdu2108,叉乘判断多边凹凸性)",主要涉及到Shape of HDU(hdu2108,叉乘判断多边凹凸性)方面的内容,对于Shape of HDU(hdu2108,叉乘判断多边凹凸性)感兴趣的同学可以参考一下。

http://acm.hdu.edu.cn/showproblem.php?pid=2108 Shape of HDU Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4481    Accepted Submission(s): 1992 Problem Description 话说上回讲到海东集团推选老总的事情,最终的结果是XHD以微弱优势当选,从此以后,“徐队”的称呼逐渐被“徐总”所取代,海东集团(HDU)也算是名副其实了。 创业是需要地盘的,HDU向钱江肉丝高新技术开发区申请一块用地,很快得到了批复,据说这是因为他们公司研发的“海东牌”老鼠药科技含量很高,预期将占全球一半以上的市场。政府划拨的这块用地是一个多边形,为了描述它,我们用逆时针方向的顶点序列来表示,我们很想了解这块地的基本情况,现在请你编程判断HDU的用地是凸多边形还是凹多边形呢? Input 输入包含多组测试数据,每组数据占2行,首先一行是一个整数n,表示多边形顶点的个数,然后一行是2×n个整数,表示逆时针顺序的n个顶点的坐标(xi,yi),n为0的时候结束输入。 Output 对于每个测试实例,如果地块的形状为凸多边形,请输出“convex”,否则输出”concave”,每个实例的输出占一行。 Sample Input 4 0 0 1 0 1 1 0 1 0 Sample Output convex 海东集团终于顺利成立了!后面的路,他们会顺顺利利吗? 欲知后事如何,且听下回分解—— Author lcy 解析: 题意:判断多边形是凹边形还是凸变形 思路:(几何基础)判断连续三点的叉积: 这里有个性质:凸边形的内角一定都是是小于180度 凹边形的内角存在在大于180度的角 232K 705 B C++ #include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #include<algorithm> using namespace std; const int maxn=10000+10; struct point { int x; int y; }p[maxn]; int Cross(point p0,point p1,point p2)//逆时针时为正 { return (p1.x-p0.x)*(p2.y-p1.y)-(p1.y-p0.y)*(p2.x-p1.x); } int main() { int n,ok,i; while(scanf("%d",&n)!=EOF) { if(n==0) break; ok=1; for(i=0;i<n;i++) scanf("%d%d",&p[i].x,&p[i].y); for(i=0;i<n;i++) { if(Cross(p[i],p[(i+1)%n],p[(i+2)%n])<0) { ok=0; break; } } if(ok) printf("convex\n"); else printf("concave\n"); } //system("pause"); return 0; }

上一篇:apue 13章 创建守护程序
下一篇:《程序猿的搬砖生活》七、爱情杂谈

相关文章

相关评论