ACM-计算几何之受到攻击——hrbust1291

题目：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1291

Description

Dota中英雄技能攻击会有一个范围，现在释放一个技能给出他的攻击范围和目标英雄的位置，问是否能攻击到。攻击范围保证是一个凸多边型

No

就是一道简单的判断点是否在凸多边形内。这里用的叉积法判断，题目中给的是逆时针方向的点序列。

第一个代码就是输出的是逆时针的。

第二个代码就是假设我们不知道是逆时针还是顺时针，再判断。

#include <iostream>
using namespace std;
struct point
{
    double x,y;
}p[110];
point hero;
int n;
// p0为起始点，求p1点在p0,p2所在直线的哪一侧
// 也可以说，p0p1构成的向量v在p0p2构成的向量w的哪一边
double cross(point p0,point p1,point p2)
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

bool isin(void)
{
    int i;
    for(i=0; i<n; ++i)
        if( cross(p[i+1],hero,p[i])<0 )    return false;
    return true;
}

int main()
{
    int i;
    while(cin>>n)
    {
        cin>>hero.x>>hero.y;
        for(i=0;i<n;++i)
            cin>>p[i].x>>p[i].y;
        p[n].x=p[0].x;
        p[n].y=p[0].y;

        if(isin())  cout<<"Yes"<<endl;
        else    cout<<"No"<<endl;
    }
    return 0;
}

#include <iostream>
using namespace std;
struct point
{
    double x,y;
}p[101];
point hero;
int n;
// p0为起始点，求p1点在p0,p2所在直线的哪一侧
// 也可以说，p0p1构成的向量v在p0p2构成的向量w的哪一边
double cross(point p0,point p1,point p2)
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

bool isin(void)
{
    int i;
    // 先判断刚开始是顺时针还是逆时针
    if( cross(p[0],hero,p[1])>0 )
    {
        for(i=1;i<n-1;++i)
            if( cross(p[i],hero,p[i+1])<=0 )    return false;
        return true;
    }
    else
    {
        for(i=1;i<n-1;++i)
            if( cross(p[i],hero,p[i+1])>=0 )    return false;
        return true;
    }
}

int main()
{
    int i;
    while(cin>>n)
    {
        cin>>hero.x>>hero.y;
        for(i=0;i<n;++i)
            cin>>p[i].x>>p[i].y;

        if(isin())  cout<<"Yes"<<endl;
        else    cout<<"No"<<endl;
    }
    return 0;
}

ACM-计算几何之受到攻击——hrbust1291,布布扣,bubuko.com

ACM-计算几何之受到攻击——hrbust1291

原文：http://blog.csdn.net/lttree/article/details/24172989