hdu 2108 Shape of HDU

2019-11-06 09:08:20

字体：大中小

来源：转载

供稿：网友

题目链接：http://acm.hdu.edu.cn/showPRoblem.php?pid=2108 题意：逆时针给你多边形上的点，让你判断这是凸多边形还是凹多边形解析：就跟凸包的判断一样，直接三个点三个点的叉乘，如果小于零，说明凹多边形

#include <cmath>#include <algorithm>#include <iostream>#include <cstdio>#include <vector>#include <cstring>using namespace std;const int maxn = 1000000+10;const double eps = 1e-5;struct point{ int x; int y; point() {} point(int _x,int _y) { x = _x; y = _y; }}a[maxn];int x_mul(point p0,point p1,point p2){ return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}bool judge(int n){ for(int i=0;i<n;i++) { if(x_mul(a[i],a[(i+1)%n],a[(i+2)%n])<0) return false; } return true;}int main(void){ int n; while(~scanf("%d",&n)&&n) { for(int i=0;i<n;i++) scanf("%d %d",&a[i].x,&a[i].y); if(judge(n)) puts("convex"); else puts("concave"); } return 0;}

上一篇：将一个数分解质因数（初级篇）

下一篇：Algorithm - KMP 字符串匹配算法