HDU-2108 Shape of HDU判断凸多边形(叉积) Apare

HDU-2108 Shape of HDU判断凸多边形(叉积)

xzc 2019.5.21

HDU题目链接<-

题意：

给出n边形按逆时针排好序的n个顶点，判断是否是凸多边形

Sample input

4
0 0 1 0 1 1 0 1
0

Sample output

convex

叉积的性质：

设向量a = (x1,y1), b = (x2,y2)
令c = a * b, 那么c是一个向量，方向垂直于a,b所在的平面
C = x1 * y2 - x2 * y1
|C|表示以向量a,b为邻边的平行四边形的面积
C的正负也是有几何意义的

若C > 0, 表示向量b在向量a的逆时针方向
若C < 0, 表示向量b在向量a的瞬时真方向
若C = 0, 表示向量b和向量a共线

我们最常用的就是性质4和性质5了

性质4课以用来求三角形的面积
性质5可以用来判断凸多边形，求凸包，判断线段相交

判断凸多边形的方法之一：

对所有顶点按照到原点或者某个点逆时针排序(题目已经给排好了)
设排好序的点为P1,P2,P3…Pn,p1,p2(循环的)
那么对于1到n的每个点Pi,它后面两个点为Pi+1和Pi+2,我们构造两个向量：
a = (pi+1.x - pi.x , pi+1.y - pi.y )
b = (pi+2.x - pi+1.x, pi+2.y - pi+1.y)
那么如果a * b的结果小于零，说明不是凸多边形

代码

/* Submit Time Judge Status Pro.ID Exe.Time Exe.Memory Code Len. Language Author 2019-05-21 19:10:12 Accepted 2108 15MS 1380K 724 B G++ apareHDU */
#include <bits/stdc++.h>
using namespace std;
bool ok(pair<int,int> p1,pair<int,int> p2,pair<int,int>p3)
{
    int x1 = p2.first - p1.first;
    int y1 = p2.second - p1.second;
    int x2 = p3.first - p2.first;
    int y2 = p3.second - p2.second;
    return 1ll*x1*y2 > 1ll*x2*y1; 
}
int main()
{
    int n,x,y;
    while(scanf("%d",&n)!=EOF&&n)
    {
        vector<pair<int,int> >v;
        for(int i=0;i<n;++i)
        {
            scanf("%d%d",&x,&y);
            v.push_back(make_pair(x,y));    
        } 
        v.push_back(v[0]);
        v.push_back(v[1]);
        bool flag = true;
        for(int i=0;i<n;++i)
        {
            if(!ok(v[i],v[i+1],v[i+2]))
            {
                flag = false;break;
            }
        }
        if(flag) printf("convex\n");
        else printf("concave\n");    
    } 
    return 0;    
}

以前用数组写的一发：

/* Submit Time Judge Status Pro.ID Exe.Time Exe.Memory Code Len. Language Author 2018-09-10 19:19:27 Accepted 2108 46MS 32680K 723 B G++ apareHDU Problem : 2108 ( Shape of HDU ) Judge Status : Accepted Language : G++ Author : apareHDU */
#include <iostream>
using namespace std;
struct Point{
    long long x,y;
    Point(long long xx=0,long long yy=0):x(xx),y(yy){}
}a[2000000+100];
long long cross(Point a,Point b)
{
    return a.x*b.y-b.x*a.y;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF&&n)
    {
        bool flag = true;
        for(int i=1;i<=n;i++)
            scanf("%lld%lld",&a[i].x,&a[i].y);
        a[n+1].x = a[1].x,a[n+1].y = a[1].y; 
        a[n+2].x = a[2].x,a[n+2].y = a[2].y; 
        for(int i=1;i<=n;i++)
        {
            Point p1(a[i+1].x-a[i].x,a[i+1].y-a[i].y);
            Point p2(a[i+2].x-a[i].x,a[i+2].y-a[i].y);
            if(cross(p1,p2)<0)
            {
                flag = false;break;    
            }    
        }
        if(flag) printf("convex\n");
        else printf("concave\n");
    }
    return 0;
}