NC14605. 画三角
描述
小学时，JYM和XJ刚刚学习了三角形，XJ提议把眼睛闭起来在纸上画三角形，巩固知识。为了让三角形更好地表示，JYM去拿了一张坐标纸（不要问为什么小学的他就有坐标纸），坐标纸的范围是[-1000,1000]。于是，XJ就在坐标纸上画了N个三角形（当然他也可能画了一条直线出来）。因为小学的他们还没有学习小数，所以所有的三角形顶点的坐标，都被JYM近似成了整数点。现在，JYM和XJ想知道这些三角形有没有将坐标原点包含在里面，请你编写程序解决这个问题。
输入描述
一个整数N(N<1000)，表示有N个三角形。接下来每一行有两个整数x(-1000<=x<=1000)和y(-1000<=y<=1000)，表示一个点的坐标；每三行的三个点构成一个三角形。
输出描述
为每个三角形输出一个YES或者NO。YES表示三角形包含了坐标原点，NO表示三角没有包含坐标原点或者坐标原点在三角形的边界上或者当前的三个点不能构成三角形。
示例1
输入:
3 1 1 -1 -1 1 0 0 0 1 0 -1 -1 1 0 0 1 -1 -1
输出:
NO NO YES
C++14(g++5.4) 解法, 执行用时: 2ms, 内存消耗: 376K, 提交时间: 2020-07-19 19:17:14
#include<iostream>
using namespace std;
int main(void)
{
int x1, x2, x3, y1, y2, y3;
long long A, B, C;
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
A = x1 * y2 - x2 * y1;
B = x2 * y3 - x3 * y2;
C = x3 * y1 - x1 * y3;
if (A*B > 0 && A*C > 0 && B*C > 0) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 3ms, 内存消耗: 488K, 提交时间: 2020-03-12 14:03:06
#include<cstdio>
using namespace std;
int T,x1,y1,x2,y2,x3,y3;
long long a,b,c;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3);
a=x1*y2-x2*y1;
b=x2*y3-x3*y2;
c=x3*y1-x1*y3;
if(a*b>0&&b*c>0)
printf("YES\n");
else
printf("NO\n");
}
}
pypy3(pypy3.6.1) 解法, 执行用时: 57ms, 内存消耗: 59448K, 提交时间: 2021-01-26 16:21:58
N = int(input())
def fn(a, b):
return a[0]*b[1]-b[0]*a[1]
for _ in range(N):
a, b, c = [list(map(int, input().split())) for _ in range(3)]
if fn(a, b)*fn(b, c)<=0 or fn(b, c)*fn(c, a)<=0:
print('NO')
else:
print('YES')
Python3(3.9) 解法, 执行用时: 16ms, 内存消耗: 2808K, 提交时间: 2020-12-17 21:06:02
def gt():
return list(map(int, input().split()))
def cr(a, b):
return a[0]*b[1]-b[0]*a[1]
n ,= gt()
while n:
n -= 1
a,b,c = gt(), gt(), gt()
print('NO') if cr(a,b)*cr(b,c)<=0 or cr(b,c)*cr(c, a)<=0 else print('YES')