2021-09-11

CCF 202006-1 线性分类器(C/C++实现 100分)


(1)问题描述

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

(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时,才表示直线能够正确分隔。
上一篇:Java Web项目搭建并部署Tomcat


下一篇:cf811 C. Vladik and Memorable Trip(dp)