#1450 : Inside Triangle

描述

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<bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N=100;
LL X[10],Y[10];

LL PX[10],PY[10];

int main()
{
	int n;
	scanf("%d",&n);
	while(n--){
		for(int i=0;i<=3;i++){
			scanf("%lld %lld",&X[i],&Y[i]);
		}

		for(int i=0;i<3;i++){
			PX[i]=X[0]-X[i+1];
			PY[i]=Y[0]-Y[i+1];
		}

		PX[3]=PX[0],PY[3]=PY[0];

		int f1=PX[0]*PY[1]-PX[1]*PY[0]>0?1:-1,f2=0;

		for(int i=0;i<3;i++){
			LL tmp=PX[i]*PY[i+1]-PX[i+1]*PY[i];
			if(tmp==0&&PX[i]*PX[i+1]+PY[i]*PY[i+1]<=0){
				f2=1;break;
			}

			tmp=tmp<0?-1:1;
			if(tmp!=f1){
				f1=0;break;
			}
		}
		//printf("f1:%d f2:%d\n",f1,f2);
		if(!f1&&!f2)printf("NO\n");
		else printf("YES\n");
	}
    return 0;
}