按:今天不舒服,就看两道水题吧。

叉积(英语:Cross product)是一种在向量空间中向量的二元运算。与点积不同,它的运算结果是一个向量而不是一个标量。两个向量的叉积写作 a × b,也称作外积(英语:Outer product)或向量积(英语:Vector product)。叉积与原来的两个向量都垂直。
叉积可以定义为 a × b = |a||b|sin<a,b>·n,而 n 是一个与 a,b 所构成的平面垂直的单位向量。
由向量 a 和 b 定义两条邻边的平行四边形,其面积为 |a||b|sin<a,b>,因此两支向量叉积的模长可视作平行四边形其面积。

计算几何基础——矢量和叉积 && 叉积、线段相交判断、凸包

SCU 2424

若叉积>0 则相对p0点,点p1在点p2的顺时针方向
若叉积<0 则相对p0点,点p1在点p2的逆时针方向
若叉积=0 则p0和p1、p2在一条直线上
(下面的题也会用到)

答案只可能是整数。

下面是 C 代码[1]:

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>
typedef struct point
{
int x,y;
}point;
point rec[5];
int cros(point a,point b,point c)
{
return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}
int main()
{
int n;
scanf("%d",&n);
while (n--)
{
for (int i=1;i<4;i++)
scanf("%d%d",&rec[i].x,&rec[i].y);
int ans=cros(rec[1],rec[2],rec[3]);
if (ans<0)
ans=-ans;
if (ans==0)
printf("Error\n");
else
printf("%d.0\n",ans);
}
return 0;
}

HDU 2108

只要有一条边向右拐(顺时针),则一定不是凸多边形。
下面是 C++ 代码[2]:

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
29
30
31
32
33
34
35
#include <iostream>
using namespace std;
struct Point {
int x,y;
};
int Cross(Point a,Point b,Point c) //叉积
{
return (c.x-a.x)*(b.y-a.y)-(c.y-a.y)*(b.x-a.x);
}
bool isConvex(Point p[],int n) //判断多边形是否是凸多边形,必须是按顺序排列的
{
int i;
p[n+1] = p[1];
p[n+2] = p[2]; //注意!!每一条边都要遍历
for(i=1;i<=n;i++)
if(Cross(p[i],p[i+1],p[i+2])>0) //是否右拐
return false;
return true;
}
int main()
{
int n;
while(cin>>n){
if(n==0) break;
int i;
Point p[1010];
for(i=1;i<=n;i++)
cin>>p[i].x>>p[i].y;
if(n<3 || isConvex(p,n)) //判断
cout<<"convex"<<endl;
else
cout<<"concave"<<endl;
}
return 0;
}


本文参考了:
1. http://jishu.y5y.com.cn/jpwang8/article/details/52420942
2. http://www.cnblogs.com/yym2013/archive/2014/04/19/3675574.html