202006-1线性分类器

题目

题目链接

题图:

image-20211130205420497

思路

在输入的时候就将对应的点分成两类。然后输入直线的时候判断这条直线是不是把这两类点分开了,如果能,那就Yes,否则No.

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
using namespace std;

struct node {
    int x, y;
};
int m, n;
const int N = 1e3;
int k = 0, kk = 0;
node type1[N], type2[N];

int main() {
    cin >> n >> m;
    int xi, yi;
    char ti;
    for (int i = 0; i < n; i++) {
        cin >> xi >> yi >> ti;
        if (ti == 'A') {
            type1[k].x = xi, type1[k].y = yi;
            k++;
        }
        if (ti == 'B') {
            type2[kk].x = xi, type2[kk].y = yi;
            kk++;
        }
    }
    int a, b, c;
    while (m--) {
        int flag = 1;
        cin >> a >> b >> c;
        /* 如果A类点在上面 */
        if (a + type1[0].x * b + type1[0].y * c > 0) {
            /* 检查A类是不是全部在上面 */
            for (int i = 0; i < k; i++) {
                if (a + type1[i].x * b + type1[i].y * c <= 0) flag = 0;
            }
            /* 检查B类点有没有混到上面的 */
            for (int i = 0; i < kk; i++) {
                if (a + type2[i].x * b + type2[i].y * c >= 0) flag = 0;
            }
        }
        /* A类点在下面 */
        else {
            for (int i = 0; i < k; i++) {
                if (a + type1[i].x * b + type1[i].y * c >= 0) flag = 0;
            }
            for (int i = 0; i < kk; i++) {
                if (a + type2[i].x * b + type2[i].y * c <= 0) flag = 0;
            }
        }

        if (flag == 1)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }

    return 0;
}
0%