Shape of HDU
Problem Description
话说上回讲到海东集团推选老总的事情，最终的结果是XHD以微弱优势当选，从此以后，“徐队”的称呼逐渐被“徐总”所取代，海东集团（HDU）也算是名副其实了。 创业是需要地盘的，HDU向钱江肉丝高新技术开发区申请一块用地，很快得到了批复，据说这是因为他们公司研发的“海东牌”老鼠药科技含量很高，预期将占全球一半以上的市场。政府划拨的这块用地是一个多边形，为了描述它，我们用逆时针方向的顶点序列来表示，我们很想了解这块地的基本情况，现在请你编程判断HDU的用地是凸多边形还是凹多边形呢？
Input
输入包含多组测试数据，每组数据占2行，首先一行是一个整数n，表示多边形顶点的个数，然后一行是2×n个整数，表示逆时针顺序的n个顶点的坐标（xi,yi），n为0的时候结束输入。
Output
对于每个测试实例，如果地块的形状为凸多边形，请输出“convex”,否则输出”concave”，每个实例的输出占一行。
Sample Input
4
0 0 1 0 1 1 0 1
0
Sample Output
convex
解题思路：
叉乘判断凸多边形。 以下参考：https://www.cnblogs.com/wmxl/p/5294620.html
向量的叉乘如X叉乘Y就是一个垂直与X和Y组成的平面的一个向量，方向是这样决定的，右手四指与X的方向相同，大拇指与四指垂直,然后四指按照这样的方向绕，从X开始,经过X与Y的锐角的方向环绕,拇指所指的方向就是X叉乘Y的方向
叉乘是三维才有意义, 这里虽然是二维的, 但可以看成第三维z是0 所以计算结果就变成了(0, 0, x1y2 - x2y1)
叉乘的几何意义是 一个垂直于两个向量的方向, 如果所有边依次相乘的方向都是一样的, 就是凸多边形, 此题因为规定了必须逆时针, 所以所有相乘都必须是正的(这个可以自己试一下就知道)
AC代码：
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std
;
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", n)
#define pc(n) printf("%c", n)
#define pdd(n,m) printf("%d %d", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sc(n) scanf("%c",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define ss(str) scanf("%s",str)
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define mem(a,n) memset(a, n, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mod(x) ((x)%MOD)
#define gcd(a,b) __gcd(a,b)
#define lowbit(x) (x&-x)
#define pii map<int,int>
#define mk make_pair
#define rtl rt<<1
#define rtr rt<<1|1
#define Max(x,y) (x)>(y)?(x):(y)
#define int long long
typedef pair
<int,int> PII
;
typedef long long ll
;
typedef unsigned long long ull
;
typedef long double ld
;
const int MOD
= 1e9 + 7;
const ll mod
= 10007;
const double eps
= 1e-9;
const ll INF
= 0x3f3f3f3f3f3f3f3fll;
inline int read(){int ret
= 0, sgn
= 1;char ch
= getchar();
while(ch
< '0' || ch
> '9'){if(ch
== '-')sgn
= -1;ch
= getchar();}
while (ch
>= '0' && ch
<= '9'){ret
= ret
*10 + ch
- '0';ch
= getchar();}
return ret
*sgn
;}
inline void Out(int a
){if(a
>9) Out(a
/10);putchar(a
%10+'0');}
int qpow(int m
, int k
, int mod
){int res
=1%mod
,t
=m
%mod
;while(k
){if(k
&1)res
=res
*t
%mod
;t
=t
*t
%mod
;k
>>=1;}return res
;}
ll
gcd(ll a
,ll b
){if(b
> a
) swap(a
,b
); return b
==0?a
: gcd(b
,a
%b
);}
ll
lcm(ll a
,ll b
){return a
/gcd(a
,b
)*b
;}
ll
inv(ll x
,ll mod
){return qpow(x
,mod
-2,mod
)%mod
;}
int t
= 1,cas
= 1;
int n
,m
;
const int N
= 1e6+15;
int primes
[N
], euler
[N
], pcnt
;
bool st
[N
];
void getEulers(int n
)
{
euler
[1] = 1;
pcnt
= 0;
for (int i
=2; i
<= n
; i
++ ){
if ( !st
[i
] ){
primes
[pcnt
++] = i
;
euler
[i
] = i
-1;
}
for ( int j
=0; primes
[j
] <= n
/i
; j
++ ){
st
[ primes
[j
]*i
] = true;
if ( i
% primes
[j
] == 0 ) {
euler
[ i
*primes
[j
] ] = euler
[i
] * primes
[j
];
break;
}
euler
[ i
*primes
[j
] ] = euler
[i
] * ( primes
[j
]-1 );
}
}
}
int Euler(int n
) {
int m
= (int)sqrt(n
+ 0.5);
int ans
= n
;
for (int i
= 2; i
<= m
; ++i
) {
if (n
% i
== 0) {
ans
= ans
/ i
*(i
- 1);
while (n
% i
== 0) n
/= i
;
}
}
if (n
> 1) ans
= ans
/ n
*(n
- 1);
return ans
;
}
int a
[N
],b
[N
];
signed main()
{
while(cin
>>n
&&n
)
{
for(int i
= 0 ; i
< n
; i
++)
cin
>>a
[i
]>>b
[i
];
b
[n
] = b
[0];a
[n
] = a
[0];
b
[n
+1] = b
[1];a
[n
+1] = a
[1];
int ans
= 1;
for(int i
= 0 ; i
< n
; i
++){
int x1
= a
[i
+2]-a
[i
+1];
int y1
= b
[i
+2]-b
[i
+1];
int x2
= a
[i
+1]-a
[i
];
int y2
= b
[i
+1]-b
[i
];
if(x1
*y2
-x2
*y1
> 0){
ans
= 0;
}
}
if(ans
)
cout
<<"convex"<<endl
;
else
cout
<<"concave"<<endl
;
}
}
