传送门:http://acm.hdu.edu.cn/showproblem.php?pid=2108
题意很简单,就是判断是凸多边形还是凹多边形。
这里用到了向量的叉积,这一块的内容基本还给老师的。。。。
再次复习下:
向量的数量积(内积,点积)
向量的向量积(外积,叉积) ,符合右手规则。
,向量积是一个伪向量,定义其方向垂直于进行叉积的两个向量且满足右手规则。
向量叉积的几何意义
计算矢量叉积是与直线和线段相关算法的核心部分。
1.向量的叉积的模表示这两个向量围成的平行四边形的面积。
设矢量P = ( x1, y1 ),Q = ( x2, y2 ),则矢量叉积定义为由(0,0)、p1、p2和p1+p2所组成的平行四边形的带符号的面积,即:P×Q = x1*y2 – x2*y1,其结果是一个伪矢量。
显然有性质 P × Q = – ( Q × P ) 和 P × ( – Q ) = – ( P × Q )。
2.叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系:
若 P × Q > 0 , 则P在Q的顺时针方向。
若 P × Q < 0 , 则P在Q的逆时针方向。
若 P × Q = 0 , 则P与Q共线,但可能同向也可能反向。
叉积的方向与进行叉积的两个向量都垂直,所以叉积向量即为这两个向量构成平面的法向量。
3.如果向量叉积为零向量,那么这两个向量是平行关系。
4.因为向量叉积是这两个向量平面的法向量,如果两个向量平行无法形成一个平面,其对应也没有平面法向量。所以,两个向量平行时,其向量叉积为零。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | #include<stdio.h> #include<string.h> #include<stdlib.h> struct node { int x; int y; }point[1001]; int main() { int n,i,p,q; while(scanf("%d",&n)&&n) { for(i=0;i<n;i++) { scanf("%d%d",&point[i].x,&point[i].y); } for(i=0;i<n;i++) { p=(point[(i+1)%n].x-point[i].x)*(point[(i+2)%n].y-point[(i+1)%n].y); q=(point[(i+2)%n].x-point[(i+1)%n].x)*(point[(i+1)%n].y-point[i].y); if(p<q) break;; } if(i==n)printf("convex\n"); else printf("concave\n"); } return 0; } |
文字有点像外星文字,破译不了。
其实第一幅图没有的,不知道为啥发表后就冒出那幅图,而且还是放大N倍后的样子。
字母字母,你可认得我,我可是有名的蓝儿挖,你敢不认识我吗、、、、、郁闷中