CSU 1272 1272: Karma（几何 判断点是否在三角形内）

题目链接：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1272

Description

英雄联盟是一个第三人称竞技游戏，角色天启者-卡尔玛有一个技能是灵魂连接，可以在小兵和自己之间施放一道光束，如果光束（包括光束的两个端点）恰好扫到敌军的小兵，则会对其造成伤害。现在已知卡尔玛这个技能连接到了某个友军的小兵上，在技能持续的时间内，卡尔玛相继走到了若干个点，且在任意两个相邻点之间走的是直线，你能计算出一共有多少个敌军的小兵受到了伤害吗？假设卡尔玛和所有的小兵都可以视作质点，且在技能持续时间内所有的小兵都没有移动。

Input

输入数据第一行为一个整数T (1 <= T <= 200)，表示接下来一共有T组测试数据。

对于每组测试数据，第一行包含两个整数N (1 <= N <= 1000), M (1 <= M <= 20)，N表示敌军小兵的个数，M表示卡尔玛在技能持续时间内相继走到的点的数量。接下来一行包含四个整数，前两个整数描述了技能连接的友军小兵的坐标，后两个描述了卡尔玛刚施放技能时所在的坐标。接下来一共有N行，每行均包含两个整数，分别描述了敌军N个小兵的坐标。再接下来一共有M行，每行均包含两个整数，分别描述了卡尔玛相继走到的M个点的坐标。所有坐标均为绝对值不超过105的整数。

Output

对于每组测试数据，用一行输出一个整数，表示一共有多少个敌军的小兵受到了伤害。

Sample Input

3
2 2
2 0 0 0
1 1
1 -1
0 3
0 0
2 2
2 0 0 0
1 1
1 -1
0 2
1 -1
2 1
2 0 0 0
1 0
-2 0
-1 0

Sample Output

1
2
1

HINT

Source

中南大学第七届大学生程序设计竞赛

PS:

每次判断未受过伤害的敌军的坐标，是否在卡尔玛移动后形成的新的三角形内！

代码如下：

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
const double eps = 1e-8;
const double PI = acos(-1.0);

int sgn(double x)
{
    if(fabs(x) < eps)return 0;
    if(x < 0)return -1;
    else return 1;
}
struct Point
{
    double x,y;
    Point() {}
    Point(double _x,double _y)
    {
        x = _x;
        y = _y;
    }
    Point operator -(const Point &b)const
    {
        return Point(x - b.x,y - b.y);
    }
    //叉积
    double operator ^(const Point &b)const
    {
        return x*b.y - y*b.x;
    }
    //点积
    double operator *(const Point &b)const
    {
        return x*b.x + y*b.y;
    }
    //绕原点旋转角度B（弧度值），后x,y的变化
    void transXY(double B)
    {
        double tx = x,ty = y;
        x = tx*cos(B) - ty*sin(B);
        y = tx*sin(B) + ty*cos(B);
    }
};
struct Point px[1010],dbx[10];

struct Line
{
    Point s,e;
    Line() {}
    Line(Point _s,Point _e)
    {
        s = _s;
        e = _e;
    }
    //两直线相交求交点
    //第一个值为0表示直线重合，为1表示平行，为0表示相交,为2是相交
    //只有第一个值为2时，交点才有意义
    pair<int,Point> operator &(const Line &b)const
    {
        Point res = s;
        if(sgn((s-e)^(b.s-b.e)) == 0)
        {
            if(sgn((s-b.e)^(b.s-b.e)) == 0)
                return make_pair(0,res);//重合
            else return make_pair(1,res);//平行
        }
        double t = ((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e));
        res.x += (e.x-s.x)*t;
        res.y += (e.y-s.y)*t;
        return make_pair(2,res);
    }
};

double dist(Point a,Point b)
{
    return sqrt(1.0*(a.x-b.x)*(a.x-b.x)+((a.y-b.y))*((a.y-b.y)));
}

double CalcArea(Point a,Point b,Point c,int n)
{
    Point p[3];
    p[0]=a;
    p[1]=b;
    p[2]=c;
    double res = 0;
    for(int i = 0; i < n; i++)
        res += (p[i]^p[(i+1)%n])/2;
    return fabs(res);
}

bool OnSeg(Point P,Line L)
{
    return
        sgn((L.s-P)^(L.e-P)) == 0 &&
        sgn((P.x - L.s.x) * (P.x - L.e.x)) <= 0 &&
        sgn((P.y - L.s.y) * (P.y - L.e.y)) <= 0;
}

bool ok(Point a,Point b,Point c,Point p)//P点是否在三角形abc内或者在三角形的边上
{
    Line ab=Line(a,b);
    Line ac=Line(a,c);
    Line bc=Line(b,c);
    pair<int,Point> j;
    j=ab&(ac);
    if(j.first!=2)
    {
        if(!OnSeg(p,ab) && !OnSeg(p,bc) && !OnSeg(p,ac))
            return 0;
        else
            return 1;
    }
    double spab=CalcArea(p,a,b,3);
    double spac=CalcArea(p,a,c,3);
    double spbc=CalcArea(p,c,b,3);
    double sabc=CalcArea(c,a,b,3);
    if(fabs(sabc-(spab+spbc+spac))<=eps)
        return 1;
    return 0;
}
bool vis[1010];
int main()
{
    double x,y;
    int t,n,m,i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        scanf("%lf%lf%lf%lf",&dbx[2].x,&dbx[2].y,&dbx[0].x,&dbx[0].y);
        for(i=0; i<n; i++)
            scanf("%lf%lf",&px[i].x,&px[i].y);
        int cont=0;
        memset(vis,false,sizeof vis);
        for(i=1; i<=m; i++)
        {
            scanf("%lf%lf",&x,&y);
            dbx[i%2].x=x;
            dbx[i%2].y=y;
            for(j=0; j<n; j++)
            {
                if(vis[j])
                    continue;
                if(ok(dbx[0],dbx[1],dbx[2],px[j]))
                {
                    cont++;
                    vis[j]=true;
                }
            }
        }
        printf("%d\n",cont);
    }
    return 0;
}
/*
100
2 2
2 0 0 0
1 1
1 -1
0 3
0 0
2 2
2 0 0 0
1 1
1 -1
0 2
1 -1
4 1
2 0 0 0
1 0
0 0
3 0
-2 0
-1 0

2 3
0 0 0 0
2 2
0 0
2 2
0 0
*/