CSP-CCF 202006-1 线性分类器

一、问题描述

二、解答

方法一：分类型遍历所有点

#include<iostream>
using namespace std;
char type[10000000] = { NULL };//字符型数组初始化
int x[10000000] = { 0 };
int y[10000000] = { 0 };//写在外面
int main()
{
	int m, n;
	cin >> n >> m;
	
	int o[20] = { 0 };
	int p[20] = { 0 }; 
	int q[20] = { 0 };
	for (int i = 0; i < n; i++)
	{
		cin >> x[i] >> y[i] >> type[i];
	}
	for (int j = 0; j < m; j++)
	{
		cin >> o[j] >> p[j] >> q[j];
	}
	for (int j = 0; j < m; j++)
	{ 

		int bigA = 0;//状态为A时大于0
		int smallA = 0;//状态为A时小于0
		int bigB = 0;//状态为B时大于0
		int smallB = 0;//状态为B时小于0
	for (int i = 0; i < n; i++)
	{
		if (type[i] == 'A')//！！！注意：在条件语句中，应该使用双等号(==)进行比较，而不是单个等号(=)
		{
			int proA = o[j] + p[j] * x[i] + q[j] * y[i];
			if(proA>0)
			{
				bigA++;
			}
			else if (proA < 0)
			{
				smallA++;
			}
		}
		else if (type[i] == 'B')
		{
			int proB = o[j] + p[j] * x[i] + q[j] * y[i];
			if (proB > 0)
			{
				bigB++;
			}
			else if (proB < 0)
			{
				smallB++;
			}
		}
	}
	if ((smallA==0&&bigA>0&&smallB>0&&bigB==0)|| (smallA> 0 && bigA == 0 && smallB == 0 && bigB > 0))
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}
	}
	return 0;
}

方法二：创建结构体

#include<iostream>
using namespace std;
//创建结构体
struct Point {
	int x;
	int y;
	char type;
};
struct Line {
	int o1;
	int o2;
	int o3;
};
int main()
{
	int m, n;
	cin >> n >> m;
	struct Point *p;
	p = new struct Point[n];//使用了动态内存分配 new
	struct Line *l;
	l = new struct Line[m];
	//struct Point points[n];这样写会报错“表达式必须有常量值”
	//因为使用了静态数组声明方式，
	//即将变量作为数组的长度，这样做是不被允许的，因为在编译时编译器无法确定数组的长度
	for (int i = 0; i < n; i++)
	{
		cin >> p[i].x >> p[i].y >> p[i].type;
	}
	for (int j = 0; j < m; j++)
	{
		cin >> l[j].o1 >> l[j].o2 >> l[j].o3;
	}
	char type1=NULL;
	char type2=NULL;//记得初始化，并且最好写在for循环外面
	for (int j = 0; j < m; j++)
	{
		int t1 = 0;
		int t2 = 0;
		for (int i = 0; i < n; i++)
		{
			if (l[j].o1 + l[j].o2 * p[i].x + l[j].o3 * p[i].y > 0)
			{
				
				if(t1==0)
				{
				 type1 = p[i].type;
				}
				if (p[i].type != type1)
				{
					cout << "No" << endl;
					break;
				}
				t1++;
			}
			if (l[j].o1 + l[j].o2 * p[i].x + l[j].o3 * p[i].y < 0)
			{
				
				if (t2 == 0)
				{
					type2 = p[i].type;
				}
				if (p[i].type != type2)
				{
					cout << "No" << endl;
					break;
				}
				t2++;
			}
		}
		if (t1 + t2 == n)
		{
			cout << "Yes" << endl;
		}
	}
	return 0;
}