Linear classifier (ccf20200901)

The sample input

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

Sample output

No
No
Yes

Ideas :
First build two structural arrays .

typedef struct Node{
    
	// x,y Point coordinates  F Mark  --  After substituting into the straight line, the result is less than 0 when , Will F The assignment is -1, Greater than 0 The assignment is 1
	int x, y, F; 
}Node;
Node flag1[maxn] = {
     0 }, flag2[maxn] = {
     0 };

First read the data , Judge whether the point coordinates belong to A still B, Store them separately into two structural arrays flag1,flag2 In .

// n Points of known categories  m Query linear equation expression  i Variables for traversal  x,y Point coordinates  a,b,c The coefficients of the linear equation 
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 To record belonging to A Number of point coordinates 
	}
	else{
    
		flag2[Blen].x = x;
		flag2[Blen].y = y;
		Blen++; //Blen To record belonging to B Number of point coordinates 
	}
}

Substitute the coordinates of points into the linear equation , The calculation result is greater than 0 Still less than 0, If you traverse flag1 All points in the structure array , They are all on the side of the straight line , namely F All are 1, Or both -1, Indicate belonging to A All points of are on the side of the straight line . Otherwise, on both sides of the line , If on both sides of the line , In this case, there is no need to judge flag2 了 , Go straight back to .

Judge flag2 Whether all points in the structure array are on the other side of the line is the same principle .

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;
}

The final code is as follows ：

#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 Points of known categories  m Query linear equation expression  i Variables for traversal  x,y Point coordinates  a,b,c The coefficients of the linear equation 
	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 To record belonging to A Number of point coordinates 
		}
		else{
    
			flag2[Blen].x = x;
			flag2[Blen].y = y;
			Blen++; //Blen To record belonging to B Number of point coordinates 
		}
	}

	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;
}