[数据结构与算法]2020-6 CCF 线性分类器 （100分）

?思路：

当开始想着讨论斜率大于0和小于0的几种情况。但转念一想，一条直线，点的分布无非就是直线上部分，直线下部分，由于题目给定处于直线上不考虑。所以，将的值分为小于0和大于0两种情况。统一规定，以l表示计算结果小于0，以r表示计算结果大于0。分别计算A,B对应的l和r的值。当且仅当lA=0且rB=0，或者 lB=0且rA=0时，直线将A,B完全分隔开。

代码：

#include<iostream>
using namespace std;
int main()
{
	int n,m;
	cin>>n>>m;
	int x[n],y[n];
	char ch[n];
	int a,a0,a1;
	int i=0;
	for(int i=0;i<n;i++)
	{
		cin>>x[i]>>y[i]>>ch[i];
	}
	for(int j=0;j<m;j++)
	{
		cin>>a>>a0>>a1;
		int l1=0,l2=0,r1=0,r2=0;
		for(int k=0;k<n;k++)
		{
			int sum;
			if(ch[k]=='A')
			{
				sum=a+a0*x[k]+a1*y[k];
				if(sum>0)
				r1++;
				else
				l1++;
			}
			if(ch[k]=='B')
			{
				sum=a+a0*x[k]+a1*y[k];
				if(sum>0)
				r2++;
				else
				l2++;
			}	
		}
		if((l1==0&&r2==0)||(l2==0&&r1==0))
		{
			cout<<"Yes"<<endl; 
		}
		else
		cout<<"No"<<endl;
		
	 } 
	 return 0;
}

?