线性分类器(CCF20200901)

样例输入

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

思路:
先构建两个结构体数组。

typedef struct Node{
    
	// x,y点坐标 F标记 -- 代入直线后结果小于0时，则将F赋值为-1，大于0则赋值为1
	int x, y, F; 
}Node;
Node flag1[maxn] = {
     0 }, flag2[maxn] = {
     0 };

首先读取数据，判断点坐标是属于A还是B，将他们分开存入两个结构体数组flag1,flag2之中。

// n个已知类别的点 m个查询直线方程表达式 i遍历用的变量 x,y点坐标 a,b,c直线方程的各个系数
int n, m, i, x, y, a, b, c;
char type;
string ss, line;
	
getline(cin, line);
stringstream L(line);
L >> n >> m;
for (i = 0; i < n;i++){
    
	getline(cin, line);
	stringstream ss(line);
	ss >> x >> y >> type;
	if (type == 'A'){
    
		flag1[Alen].x = x;
		flag1[Alen].y = y;
		Alen++; //Alen来记录属于A的点坐标个数
	}
	else{
    
		flag2[Blen].x = x;
		flag2[Blen].y = y;
		Blen++; //Blen来记录属于B的点坐标个数
	}
}

将点的坐标代入直线方程，计算结果是大于0还是小于0，若遍历一遍flag1结构体数组中全部的点，它们全都是在直线的一侧，即F都是1，或者都是-1，表明属于A的点全部在直线一侧。否则在直线两侧，如果在直线两侧，这种情况下就不用判断flag2了，直接返回。

判断flag2结构体数组中全部的点是否在直线另一侧也是同样的原理。

int myfun(int a, int b, int c)
{
    
	int i;
	for (i = 0; i < Alen; i++){
    
		if (i == 0){
    
			if ((a + b * flag1[i].x + c * flag1[i].y) < 0){
    
				flag1[i].F  = -1;
			}
			else{
    
				flag1[i].F = 1;
			}
		}
		else{
    
			if ((a + b * flag1[i].x + c * flag1[i].y) < 0 && flag1[i - 1].F == -1){
    
				flag1[i].F = -1;
			}
			else if ((a + b * flag1[i].x + c * flag1[i].y) > 0 && flag1[i - 1].F == 1){
    
				flag1[i].F = 1;
			}
			else{
    
				break;
			}
		}
	}
	if (i != Alen) return -1;

	for (i = 0; i < Blen; i++){
    
		if (i == 0){
    
			if ((a + b * flag2[i].x + c * flag2[i].y) < 0){
    
				flag2[i].F = -1;
			}
			else{
    
				flag2[i].F = 1;
			}
		}
		else{
    
			if ((a + b * flag2[i].x + c * flag2[i].y) < 0 && flag2[i - 1].F == -1){
    
				flag2[i].F = -1;
			}
			else if ((a + b * flag2[i].x + c * flag2[i].y) > 0 && flag2[i - 1].F == 1){
    
				flag2[i].F = 1;
			}
			else{
    
				break;
			}
		}
	}
	if (i != Blen) return -1;
	return 1;
}

最终代码如下：

#include<iostream>
#include<string>
#include<sstream>
const int maxn = 1010;
using namespace std;
int Alen = 0, Blen = 0;
typedef struct Node{
    
	int x, y, F;
}Node;
Node flag1[maxn] = {
     0 }, flag2[maxn] = {
     0 };
int myfun(int a, int b, int c)
{
    
	int i;
	for (i = 0; i < Alen; i++){
    
		if (i == 0){
    
			if ((a + b * flag1[i].x + c * flag1[i].y) < 0){
    
				flag1[i].F  = -1;
			}
			else{
    
				flag1[i].F = 1;
			}
		}
		else{
    
			if ((a + b * flag1[i].x + c * flag1[i].y) < 0 && flag1[i - 1].F == -1){
    
				flag1[i].F = -1;
			}
			else if ((a + b * flag1[i].x + c * flag1[i].y) > 0 && flag1[i - 1].F == 1){
    
				flag1[i].F = 1;
			}
			else{
    
				break;
			}
		}
	}
	if (i != Alen) return -1;

	for (i = 0; i < Blen; i++){
    
		if (i == 0){
    
			if ((a + b * flag2[i].x + c * flag2[i].y) < 0){
    
				flag2[i].F = -1;
			}
			else{
    
				flag2[i].F = 1;
			}
		}
		else{
    
			if ((a + b * flag2[i].x + c * flag2[i].y) < 0 && flag2[i - 1].F == -1){
    
				flag2[i].F = -1;
			}
			else if ((a + b * flag2[i].x + c * flag2[i].y) > 0 && flag2[i - 1].F == 1){
    
				flag2[i].F = 1;
			}
			else{
    
				break;
			}
		}
	}
	if (i != Blen) return -1;
	return 1;
}
int main(){
    
	// n个已知类别的点 m个查询直线方程表达式 i遍历用的变量 x,y点坐标 a,b,c直线方程的各个系数
	int n, m, i, x, y, a, b, c;
	char type;
	string ss, line;
	
	getline(cin, line);
	stringstream L(line);
	L >> n >> m;
	for (i = 0; i < n;i++){
    
		getline(cin, line);
		stringstream ss(line);
		ss >> x >> y >> type;
		if (type == 'A'){
    
			flag1[Alen].x = x;
			flag1[Alen].y = y;
			Alen++; //Alen来记录属于A的点坐标个数
		}
		else{
    
			flag2[Blen].x = x;
			flag2[Blen].y = y;
			Blen++; //Blen来记录属于B的点坐标个数
		}
	}

	for (i = 0; i < m; i++){
    
		getline(cin, line);
		stringstream ss(line);
		ss >> a >> b >> c;
		if (myfun(a, b, c)>0)  cout << "Yes" << endl;
		else  cout << "No" << endl;
	}
	return 0;
}