CCF 202006-1 线性分类器（C/C++实现 100分）

---

（1）问题描述

• 题干过长，故意描述的看起来很难，实际是难度并不大，需要细心分析。
  
  
  

（2）代码

#include<iostream>
using namespace std;
int site[1001][2];//存放坐标 
int result[1001];//存放结果，为1表示可以分隔
char ch[1001];//存放A/B类型

int main() {
	int n,m,a0,a1,b0,b1,temp;
	int a,b,c;	
	cin>>n>>m;
	//输入点坐标和类别
	for(int i=0;i<n;i++) {
		cin>>site[i][0]>>site[i][1]>>ch[i];
	}
	
	//输入参数组，每次输完一组都要对所有点进行判断
	for(int i=0;i<m;i++) {
		cin>>a>>b>>c;
		a0=0,a1=0,b0=0,b1=0;//重新初始化，防止对下一次遍历的影响
		
		// 判断点在直线的哪一边 
		for(int k=0;k<n;k++) {
			//线性回归方程，判断点坐标与0的关系，确定其位于哪一侧
			temp=a+b*site[k][0]+c*site[k][1];
			if(temp>0&&ch[k]=='A') a0++;//一侧的A点个数
            if(temp<0&&ch[k]=='A') a1++;//另一侧的A点个数
            if(temp>0&&ch[k]=='B') b0++;//一侧的B点个数
            if(temp<0&&ch[k]=='B') b1++;//另一侧的B点个数
		}
		
		//当不同侧的A和B点总和为n时，表示可以分隔
		if(a0+b1==n || a1+b0==n) {
			result[i]=1;//表示可以分隔 
		}
	}
	
	//根据标记数组result，打印结果
	for(int i=0;i<m;i++) {
		if(result[i]==1) {
			cout<<"Yes"<<endl;
		} 
		else {
			cout<<"No"<<endl; 
		}
	}
	return 0;
} 

（3）要点

• 本道题涉及线性回归方程问题，通过Ax+By+c与0的比较，得出不同的点位于直线的哪一侧。
• 只有当分别位于直线两侧的A与B点数量加起来为总数n时，才表示直线能够正确分隔。