Hust oj 1642 多边形-1（叉乘）_综合

多边形-1

Time Limit: 1000 MS

Memory Limit: 32768 K

Total Submit: 68(37 users)

Total Accepted: 43(36 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

对于有公共端点的线段p0p1和p1p2，通过计算(p2 - p0) × (p1 - p0)的符号便可以确定折线段的拐向：

若(p2 - p0) × (p1 - p0) > 0,则p0p1在p1点拐向右侧后得到p1p2。

若(p2 - p0) × (p1 - p0) < 0,则p0p1在p1点拐向左侧后得到p1p2。

若(p2 - p0) × (p1 - p0) = 0,则p0、p1、p2三点共线。

然后跑一边所有点就行了。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;const int Maxn = 1005;
int x[Maxn];
int y[Maxn];int cross(int x0,int y0,int x1,int y1,int x2,int y2)
{int re = (x2 - x0) * (y1 - y0) - (x1 - x0) * (y2 - y0);return re;
}int main()
{int n;while(~scanf("%d",&n) && n){for(int i=0;i<n;i++){scanf("%d%d",&x[i],&y[i]);}x[n] = x[0];y[n] = y[0];x[n+1] = x[1];y[n+1] = y[1];int flag = 0;for(int i=2;i<=n+1;i++){int ans = cross(x[i-2],y[i-2],x[i-1],y[i-1],x[i],y[i]);if(ans > 0){flag = 1;break;}}if(flag)printf("Concave\n");elseprintf("Convex\n");}
}