文章目录
一、题目二、算法思想三、代码
一、题目
二、算法思想
题目需要我们求解的问题：判断一条直线是否将全部的点划分成A类和B类两个部分。
要解决这个问题可以先将点分为两个部分：
位于直线上方的位于直线以下的
这样就不需要判断上方是A类还是下方是B类。 只要每个部分中的点类型都相同，那就表示这条直线能够完美划分这些点。
要判断一个点（x，y）和一条直线ax + by + c = 0的相对位置时可以直接将点的坐标带入到直线的方程中如果ax + by +c的值为0时，表示点在直线值为正数时，表示点在直线上方值为负数时，表示点在直线的下方。
存储结构使用了列表，直线和点都有三个对应的数据，创建两个列表分别进行存储。然后循环输入点或直线的三个数据，将三条数据以列表的形式存放到较大的列表中。之后就是双重循环，外层先遍历直线对应的列表，再内层遍历每个点。
在遍历直线时，提前定义了两个列表，分别用于存放直线上方和直线下方点的类型。对于一个列表，在确定好各部分点类型后使用python的集合类型将两个列表去重如果去重过后的元素值不止一个时，就说明这个部分的点类型既有A也有B，所以可以直接判断出直线是否完美划分这些点。
三、代码
n
,m
= input().split
()
n
= int(n
)
m
= int(m
)
data
= []
line
= []
for i
in range(n
):
x
,y
,kind
= input().split
()
x
= int(x
)
y
= int(y
)
data
.append
([x
,y
,kind
])
for i
in range(m
):
x1
,x2
,x3
= input().split
()
x1
= int(x1
)
x2
= int(x2
)
x3
= int(x3
)
line
.append
([x1
,x2
,x3
])
for i
in range(m
):
kind_up
= []
kind_down
= []
for j
in range(n
):
if line
[i
][0]+line
[i
][1]*data
[j
][0]+line
[i
][2]*data
[j
][1]>0:
kind_up
.append
(data
[j
][2])
if line
[i
][0]+line
[i
][1]*data
[j
][0]+line
[i
][2]*data
[j
][1]<0:
kind_down
.append
(data
[j
][2])
kind_up
= set(kind_up
)
kind_down
= set(kind_down
)
if len(kind_up
)==1 and len(kind_down
)==1:
print("Yes")
else:
print("No")
