csp ccf线性分类器【c语言】（2020.6 题一）

答题思路：先分AB类点，后判断是否A类点都在同一侧，B类点都在另一侧。

参考代码

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
	int n,m; //定义输入的点数n，线性分类条数m； 
	scanf("%d%d",&n,&m);
	int x, y, i, j;
	char types; // 分类A、B点。 
	int xa[n], ya[n], xb[n], yb[n];
	int counta = 0, countb = 0; // 统计A、B点的个数。 
	int k[m][3]; // 线性分类条数m的三个值 
	int flagA = 0, flagB = 0; 
	
	for(i = 0; i < n; i++){
		scanf("%d%d %c", &x, &y, &types);
		if(types == 'A'){ //判断是否为A点，并统计个数。 
			xa[counta] = x;
			ya[counta] = y;
			counta++;
		}else{
			xb[countb] = x;
			yb[countb] = y;
			countb++;
		}
	}

	for (i = 0; i < m; i++){ // 循环输入线性分类器的值 
		scanf("%d%d%d", &k[i][0], &k[i][1], &k[i][2]);
	}
	
	for(i = 0; i < m; i++){ // 循环判断每一条线性分类器是否符合 
		for(j = 0; j < counta; j++){ //判断A类点，如果都在同一侧 ，则flagA要么就等于counta，要么就为0 
			if(k[i][0] + xa[j]*k[i][1] + ya[j]*k[i][2] > 0){
				flagA++;
			}
		}
		for(j = 0; j < countb; j++){//判断B类点，如果都在同一侧 ，则flagB要么就等于countb，要么就为0 
			if(k[i][0] + xb[j]*k[i][1] + yb[j]*k[i][2] > 0){
				flagB++;
			}
		}
		// 将A、B点完美分开的话，即flagA 与 flagB 一个为0，一个为本身点的个数。 
		if(flagA == counta && flagB == 0){
			printf("Yes\n");
		}else if(flagA == 0 && flagB == countb){
			printf("Yes\n");
		}else {
			printf("No\n");
		}
		flagA = 0; // 重新归零以备下个循环判断 
		flagB = 0;
	}
	return 0;
}

题目链接：http://118.190.20.162/view.page?gpid=T105

【题目描述】
考虑一个简单的二分类问题——将二维平面上的点分为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

【样例 1 输出】

No
No
Yes

【样例 1 解释】
只有第 3 个查询给出的直线能将A、B 两类点完美分隔