HDU/HDOJ 2108 Shape of HDU

传送门：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;
}