哈理工OJ 1642 多边形-1【计算几何】【判断凸凹包】

多边形-1

Time Limit: 1000 MS Memory Limit: 32768 K Total Submit: 61(34 users) Total Accepted: 37(32 users) Rating:  Special Judge: No

Description

任意给定一个多边形，判断它是凸还是凹。多边形的顶点以逆时针方向的序列来表示。

Input

输入包含多组测试数据，每组数据占两部分。第一行是一个整数n，表示多边形顶点的个数，接下来n（3<=n<=1000）行每行两个整数，表示逆时针顺序的n个顶点的坐标（xi,yi）（-1000<=xi,yi<=1000）。 n为0的时候结束输入。

Output

对于每组测试样例，如果多边形的形状为凸多边形，请输出“Convex”,否则输出”Concave”，每组样例的输出占一行。

Sample Input

4 0 0 1 0 1 1 0 1 5 0 0 1 -1 1 1 -1 1 -1 -1 0

Sample Output

Convex Concave

一道裸的判断凸凹包的题目，思路形成比较简单。我们拿样例1来说明这个问题：

我们知道，向量叉乘的求出的值要么正，要么负，要么等于0.叉乘>0说明线段是顺时针形成的，反之，逆时针形成的。我们这里拿出样例1中的点，规定编号为A,B,C,D

我们先对ABC判断，如果AB在BC的逆时针方向，那么这里就能形成一个凸角、

我们再对BCD判断，如果BC爱CD的逆时针方向，那么这里也能形成一个凸角、

依次类推，我们能得到这样的结论：如果这样判断n次，全部的边都是在逆时针方向，那么这个多边形就是凸多边形，如果有某三个点没有形成逆时针，那么就是凹多边形、

这里口述并不是完全好理解，这里大家可以画画图。

直接上AC代码：

#include
#include
using namespace std;
int x[12121212];
int y[12121212];
int main()
{int n;while(~scanf("%d",&n)){if(n==0)break;for(int i=0;i