题目

【题目描述】 考虑一个简单的二分类问题——将二维平面上的点分为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输入】

9 3
1 1 A
1 0 A
1 -1 A
2 2 B
2 3 B
0 1 A
3 1 B
1 3 B
2 0 A
0 2 -3
-3 0 2
-3 1 1

【样例1输出】

NO
NO
YES

代码

#include<bits/stdc++.h>
using namespace std;

const int N=1000;
struct node
{
    int x;
    int y;
    char type;
}a[N];

bool cmp(node a,node b)
{
    return a.type<b.type;
}

int main()
{
    int n,m;
    int theta0,theta1,theta2,pre,result,flag=1;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>a[i].x>>a[i].y>>a[i].type;
    }
    sort(a,a+n,cmp);

    for(int i=0;i<m;i++)
    {
        cin>>theta0>>theta1>>theta2;
        for(int j=0;j<n;j++)
        {
            result=(theta0+theta1*a[j].x+theta2*a[j].y>0)?1:0;
            if(j==0)
                flag=1;
            else if((result!=pre&&a[j].type==a[j-1].type)(result==pre&&a[j].type!=a[j-1].type))
            {
                flag=0;
            }
            pre=result;
        }
        if(flag)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    return 0;
}