csp试题1：线性分类器

题目

题目描述
      考虑一个简单的二分类问题——将二维平面上的点分为 A 和 B 类。
      训练数据包含 n 个点，其中第 i 个点（1 <= i <= n）可以表示为一个三元组（x_i, y_i, type_i），即该点的横坐标，纵坐标，和类别。
      在二维平面上，任意一条直线可以表示为Θ₀ + Θ₁x + Θ₂y = 0 的形式，即由Θ₀、Θ₁、Θ₂三个参数确定该直线，且满足Θ₁、Θ₂不同时为0。
      基于这 n 个已知类别的点，我们想要在平面上找到一条直线作为一个线性分类器。具体来说，这条线要把训练数据中的 A、B 两类点完美分隔开来，即一侧只有 A 类点、另一侧只有 B 类点。这样，对于任意一个的位置类别的点，我们就可以根据它是位于直线的那一侧来预测它的类别了。
      在本题中我们仅需要处理 m 个如下查询：给定一条直线，判断它是否能将训练数据中的 A、B两类点完美分开。
输入格式
      从标准输入读入数据。
      输入共 n+m+1行。
      第一行包含用空格分隔的两个正整数 n 和 m，分别表示 点 和 查询 的个数。
      第二行到第 n+1 行依次输入 n 个点的信息。第 i+1 行（1<=i<=n）包含用空格分隔的三项 x_i, y_i 和 type_i，分别表示第 i 个点的横、纵坐标和类别，其中坐标为整数、类别为一个大写英文字母 A 或 B。
      第 n+2 行到第 n+m+1行依次输入 m 个查询。第 j+n+1 行（1<=j<=m）包含用空格分割的三个整数Θ₀、Θ₁ 和 Θ₂，表示第 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

输出：

No
No
Yes

解释：

子任务

• 输入数据保证不存在恰好落在给定直线上的点；
• 0<n<=10³、0<m<=20，且 A、B 两类点的数量均不为0；
• 所有点的坐标和给定直线的三个参数均为整数，且绝对值<=10⁶
• 任意两个点的坐标不完全相同。
  

分析

1. 如何使用直线去分类：通过三个 Θ 值我们得到了一个直线等式，将点的x、y坐标带入直线算式中，得出的结果由三种：大于0、小于0、等于0。等于0的点不考虑，通过结果大于0还是小于0就将点分成了两类。
2. 当一条直线可以将数据完美二分类时，标签为 A 的点可能会是大于0的那一类，也可能是小于0的哪一类。

代码

import java.util.Scanner;

/**
 * csp测试
 * 题目：202006-1 线性分类器
 * @author dxt
 *
 */
public class Main {
	public static void main(String[] args){
		//1.1  接收数据 n和m
		int n, m;
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		m = scan.nextInt();
		//System.out.println(n);
		
		//1.2 接收点的坐标数据 和 对应分类
		int[][] datas = new int[n][2];
		char[] types = new char[n];
		for(int i=0; i<n; i++){
			datas[i][0] = scan.nextInt();	//横坐标
			datas[i][1] = scan.nextInt();	//纵坐标
			types[i] = scan.next().charAt(0);	//types
		}
		//1.3 创建theta[]，保存每次直线的参数
		int[] theta = new int[3];
		
		//1.4 创建outcome[], 保存分类的结果
		boolean[] outcome = new boolean[m];
		
		//2. 不断接收参数，然后计算 --> 判断 --> 分类 --> 设置结果
		boolean AisUp = true;	//标签为A的点通过计算结果是否大于0
		for(int i=0; i<m; i++){
			//2.1 接收这次分类的直线数据
			for(int j=0; j<3; j++){
				theta[j] = scan.nextInt();
			}
			
			//2.2 使用这条直线对n个点进行分类
			//2.2.1  先对第一个点进行计算，判断A、B标签应该在直线哪一侧
			int result = theta[0] + (theta[1]*datas[0][0]) + (theta[2]*datas[0][1]);
			//2.2.2 依据 结果 和 type 对 A 、 B 进行分侧
			if(types[0] == 'A'){
				if(result > 0){		
					AisUp = true;	//A标签的点结果大于0
				}else{
					AisUp = false;	//A标签的点结果小于0
				}
			}else if(types[0] == 'B'){
				if(result > 0){
					AisUp = false;	//B标签的点结果大于0
				}else{
					AisUp = true;	//B标签的点结果小于0
				}
			}
			//2.2.3 从第二个点开始处理
			for(int k=1; k<n; k++){
				//2.2.3.1 将点的坐标代入直线方程，计算结果
				result = theta[0] + (theta[1]*datas[k][0]) + (theta[2]*datas[k][1]);
				//2.2.3.2 判断是否分类正确
				if(AisUp){	//A标签的数据>0
					if((types[k]=='A') && (result > 0)){
						//则分类正确
						outcome[i] = true;	//设置为true
					}else if((types[k]=='A') && (result < 0)){
						//分类错误
						outcome[i] = false;	//设置为false
						break;	//已经分类错误了，不用再去计算剩余数据
					}else if((types[k]=='B') && (result > 0)){
						//分类错误
						outcome[i] = false;	
						break;	
					}else if((types[k]=='B') && (result < 0)){
						//分类正确
						outcome[i] = true;	
					}
				}else{	//A标签的数据<0
					if((types[k]=='A') && (result > 0)){
						//则分类错误
						outcome[i] = false;	//设置为false
						break;	//已经分类错误了，不用再去计算剩余数据
					}else if((types[k]=='A') && (result < 0)){
						//分类正确
						outcome[i] = true;	//设置为true
					}else if((types[k]=='B') && (result > 0)){
						//分类正确
						outcome[i] = true;	
					}else if((types[k]=='B') && (result < 0)){
						//分类错误
						outcome[i] = false;
						break;
					}
				}
			}
		}
		
		//3. 输出结果
		for(int i=0; i<m; i++){
			if(outcome[i]){
				System.out.println("Yes");
			}else{
				System.out.println("No");
			}
		}
	}
}

总结

1. Scanner无法直接接收字符数据。

本文地址：https://blog.csdn.net/qq_37665301/article/details/107475061