题目
【题目描述】 考虑一个简单的二分类问题——将二维平面上的点分为A和B两类。 训练数据包含n个点,其中第i个点(1≤i≤n)可以表示为一个三元组(x,y,type),即该点的横坐标、纵坐标和类别。 在二维平面上,任意一条直线可以表示为a+bx+cy=0的形式,即由a、b和c三个参数确定该直线,且满足b、c不同时为0。 基于这个已知类别的点,我们想要在平面上找到一条直线作为一个线性分类器。 具体来说,这条线要把训练数据中的A、B两类点完美分隔开来,即一侧只有A类点、另一侧只有B类点。这样,对于任意一个的未知类别的点,我们就可以根据它是位于直线的哪一侧来预测它的类别了。 在本题中我们仅需要处理m个如下查询:给定一条直线,判断它是否能将训练数据中的A、B两类点完美分开。
【输入格式】 从标准输入读入数据。 输入共n+m+1行 第一行包含用空格分隔的两个正整数和m,分别表示点和查询的个数。 第二行到第n+1行依次输入n个点的信息。第i+1行(1≤i≤n)包含用空格 分隔的三项x、y和type,分别表示第i个点的横、纵坐标和类别,其中坐标为整数、类别为一个大写英文字母A或B。 第n+2行到第n+m+1行依次输入m个查询。第j+n+1行(1≤j≤m)包含用空格分隔的三个整数a,b和c,表示第J个查询中给定直线的三个参数。
【输出格式】 输出到标准输出。 输出共m行,每行输出一个字符串. 第j行(1≤j≤m)输出的字符串对应第j个查询的结果:如果给定直线可以完美分隔A、B两类点,则输出Yes:否则输出No。
【样例1输入】
1 | 9 3 |
【样例1输出】
1 | NO |
代码
1 |
|