题目描述
考虑一个简单的二分类问题——将二维平面上的点分为 A 和 B 类。
训练数据包含 n 个点,其中第 i 个点(1 <= i <= n)可以表示为一个三元组(xi, yi, typei),即该点的横坐标,纵坐标,和类别。
在二维平面上,任意一条直线可以表示为Θ0 + Θ1x + Θ2y = 0 的形式,即由Θ0、Θ1、Θ2三个参数确定该直线,且满足Θ1、Θ2不同时为0。
基于这 n 个已知类别的点,我们想要在平面上找到一条直线作为一个线性分类器。具体来说,这条线要把训练数据中的 A、B 两类点完美分隔开来,即一侧只有 A 类点、另一侧只有 B 类点。这样,对于任意一个的位置类别的点,我们就可以根据它是位于直线的那一侧来预测它的类别了。
在本题中我们仅需要处理 m 个如下查询:给定一条直线,判断它是否能将训练数据中的 A、B两类点完美分开。
输入格式
从标准输入读入数据。
输入共 n+m+1行。
第一行包含用空格分隔的两个正整数 n 和 m,分别表示 点 和 查询 的个数。
第二行到第 n+1 行依次输入 n 个点的信息。第 i+1 行(1<=i<=n)包含用空格分隔的三项 xi, yi 和 typei,分别表示第 i 个点的横、纵坐标和类别,其中坐标为整数、类别为一个大写英文字母 A 或 B。
第 n+2 行到第 n+m+1行依次输入 m 个查询。第 j+n+1 行(1<=j<=m)包含用空格分割的三个整数Θ0、Θ1 和 Θ2,表示第 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
解释:
子任务
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");
}
}
}
}
本文地址:https://blog.csdn.net/qq_37665301/article/details/107475061
如对本文有疑问, 点击进行留言回复!!
关于在IDEA中SpringBoot项目中activiti工作流的使用详解
视频编辑工具ACDSee Luxea Video Editor安装及激活图文教程
java spring整合junit操作(有详细的分析过程)
网友评论