小小知识

r囧r小猫 2022-06-15 22:53 187阅读 0赞

**fill\_n函数的作用是**：给你一个起始点，然后再给你一个数值count和val。把从起始点开始依次赋予count个元素val的值。

判断一个点是否在三角形内部

如果三角形PAB、PAC和PBC的面积之和与三角形ABC的面积相等，则可判定点P在三角形ABC内（包括在三条边上）。

已知三角形顶点A、B、C)的坐标分别为（Ax, Ay）、（Bx, By）、（Cx, Cy），即可计算其面积：  
     S = |(Ax \* By + Bx \* Cy + Cx \* Zy - Ay \* Bx- By \* Cx - Cy \* Ax) / 2|

[点击打开链接][Link 1]

### 描述 ###

Determine if a point is inside a 2D triangle.

### 输入 ###

The first line contains an integer T denoting the number of test case. (1 <= T <= 10)

The following T lines each contain 8 integers, Px, Py, Ax, Ay, Bx, By, Cx, Cy. P denotes the point. ABC denotes the triangle. The coordinates are within \[-1000000, 1000000\].

### 输出 ###

For each test case output YES or NO denoting if the point is inside the triangle. Note that the point is considered inside the triangle if the point is just on some side of the triangle.

样例输入

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

样例输出

YES  
    NO

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int A(long long px,long long py,long long ax,long long ay,long long bx,long long by,long long cx,long long cy)
    {
        long long s1,s2,s3,s4;
        s1=abs(ax*by+bx*cy+cx*ay-ay*bx-by*cx-cy*ax);
        s2=abs(ax*by+bx*py+px*ay-ay*bx-by*px-py*ax);
        s3=abs(bx*cy+cx*py+px*by-by*cx-cy*px-py*bx);
        s4=abs(ax*cy+cx*py+px*ay-ay*cx-cy*px-py*ax);
        if(s1==s2+s3+s4)
            return 1;
        return 0;
    }
    int AA(long long px,long long py,long long ax,long long ay,long long bx,long long by,long long cx,long long cy)    //判断是否在边上；利用斜率；
    {
        long long s1,s2,s3,s4,s5,s6;
        s1=(ay-py)*(px-bx);
        s2=(ax-px)*(py-by);
        s3=(ay-py)*(px-cx);
        s4=(ax-px)*(py-cy);
        s5=(cy-py)*(px-bx);
        s6=(cx-px)*(py-by);
        if(s1==s2||s3==s4||s5==s6)
            return 0;
        return 1;
    }
    int AAA(long long px,long long py,long long ax,long long ay,long long bx,long long by,long long cx,long long cy) //判断是否在顶点上；
    
    {
        if((px==ax&&py==ay)||(px==bx&&py==by)||(px==cx&&py==cy))
            return 0;
        return 1;
    }
    int main()
    {
    	int t;
    	long long px,py,ax,ay,bx,by,cx,cy;
    	scanf("%d",&t);
    	while(t--)
        {
            scanf("%lld %lld %lld %lld %lld %lld %lld %lld",&px,&py,&ax,&ay,&bx,&by,&cx,&cy);
            if(A(px,py,ax,ay,bx,by,cx,cy)&&AA(px,py,ax,ay,bx,by,cx,cy)&&AAA(px,py,ax,ay,bx,by,cx,cy))
                printf("YES\n");
            else
                printf("NO\n");
        }
    	return 0;
    }

[Link 1]: http://hihocoder.com/contest/hihointerview28/problem/1