线性分类器

GitHub跳转原题关系图 Canvas 关系图返回列表

代入直线方程检查两类点内部同号且两类代表符号相反。

OJ: shumeng

题目 ID: CSP202006A

难度:入门

标签:模拟几何分类

日期: 2026-07-31 16:21

形式化题目

有 $n$ 个带类别 $\text{A}$ 或 $\text{B}$ 的平面点 $(x_i,y_i)$ 和 $m$ 条直线

\theta_0+\theta_1x+\theta_2y=0,

对每条直线判断它是否把两类点完全分到两侧：一侧只有 A 类点，另一侧只有 B 类点。数据保证没有任何点恰好落在直线上。

思路

把每个点 $(x,y)$ 代入直线方程，得到的值的正负号表示这个点位于直线的哪一侧。因为不会出现零，只需要比较符号。

判断步骤

记录第一个 A 点与第一个 B 点的符号，作为两类各自的代表符号；
扫描全部点：A 点都必须与 A 的代表符号相同，B 点都必须与 B 的代表符号相同；
两个代表符号还必须相反，说明两类点分居直线两侧。

三个条件全部满足时输出 Yes，否则输出 No。

先看一个朴素的两遍扫描实现，第一遍确定每类代表符号，第二遍验证所有点：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
// brute.cpp：小数据暴力解，两遍扫描先确定每类代表符号，再验证所有点。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n, query_count;
long long x[MAXN], y[MAXN];   // 点的横坐标、纵坐标
char type[MAXN];              // 点的类别：A 或 B

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> query_count;
    for (int i = 1; i <= n; i++) cin >> x[i] >> y[i] >> type[i];

    while (query_count--) {
        long long theta0, theta1, theta2;
        cin >> theta0 >> theta1 >> theta2;

        // 第一遍：确定 A、B 两类各自的代表符号
        int sign_a = 0, sign_b = 0;
        for (int i = 1; i <= n; i++) {
            long long value = theta0 + theta1 * x[i] + theta2 * y[i];
            int sign = value > 0 ? 1 : -1;
            if (type[i] == 'A' && sign_a == 0) sign_a = sign;
            if (type[i] == 'B' && sign_b == 0) sign_b = sign;
        }

        // 第二遍：验证所有点与各自类别代表符号一致，且两类符号相反
        bool correct = sign_a != sign_b;
        for (int i = 1; i <= n; i++) {
            long long value = theta0 + theta1 * x[i] + theta2 * y[i];
            int sign = value > 0 ? 1 : -1;
            if (type[i] == 'A' && sign != sign_a) correct = false;
            if (type[i] == 'B' && sign != sign_b) correct = false;
        }
        cout << (correct ? "Yes" : "No") << '\n';
    }

    return 0;
}

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n, query_count;
long long x[MAXN], y[MAXN];   // 点的横坐标、纵坐标
char type[MAXN];              // 点的类别：A 或 B

// 返回 value 的符号：正为 1，负为 -1（题目保证点不落在直线上）
int get_sign(long long value) {
    return value > 0 ? 1 : -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> query_count;
    for (int i = 1; i <= n; i++) cin >> x[i] >> y[i] >> type[i];

    while (query_count--) {
        long long theta0, theta1, theta2;
        cin >> theta0 >> theta1 >> theta2;

        int sign_a = 0, sign_b = 0;   // A 类与 B 类各自的代表符号
        bool correct = true;
        for (int i = 1; i <= n; i++) {
            // 代入直线方程，结果的正负表示点在直线的哪一侧
            long long value = theta0 + theta1 * x[i] + theta2 * y[i];
            int sign = get_sign(value);
            if (type[i] == 'A') {
                if (sign_a == 0) sign_a = sign;
                else if (sign_a != sign) correct = false;
            } else {
                if (sign_b == 0) sign_b = sign;
                else if (sign_b != sign) correct = false;
            }
        }
        // 两类点必须在直线两侧，即代表符号相反
        if (sign_a == sign_b) correct = false;
        cout << (correct ? "Yes" : "No") << '\n';
    }

    return 0;
}

复杂度

每条查询扫描全部 $n$ 个点，时间复杂度为 $O(nm)$ ，空间复杂度为 $O(n)$ 。

总结

线性分类器的“分隔”条件不需要做复杂的几何运算。把所有点代入同一个一次式，检查同类同号、异类异号即可。

时间限制： 1.0 秒

空间限制： 512 MB

题目描述

考虑一个简单的二分类问题——将二维平面上的点分为 A 和 B 两类。

训练数据包含 $n$ 个点，其中第 $i\ (1 \leq i \leq n)$ 个点可以表示为一个三元组 $(x_i, y_i, type_i)$ ，即该点的横坐标、纵坐标和类别。

在二维平面上，任意一条直线可以表示为 $\theta_0 + \theta_1 x + \theta_2 y = 0$ 的形式，即由 $\theta_0,\theta_1,\theta_2$ 三个参数确定该直线，且满足 $\theta_1,\theta_2$ 不同时为 $0$ 。

基于这 $n$ 个已知类别的点，我们想要在平面上找到一条直线作为一个线性分类器。具体来说，这条线要把训练数据中的 A、B 两类点完美分隔开来，即一侧只有 A 类点、另一侧只有 B 类点。这样，对于任意一个的未知类别的点，我们就可以根据它是位于直线的哪一侧来预测它的类别了。

在本题中我们仅需要处理 $m$ 个如下查询：给定一条直线，判断它是否能将训练数据中的 A、B 两类点完美分开。

输入格式

从标准输入读入数据。

输入共 $n+m+1$ 行。

第一行包含用空格分隔的两个正整数 $n$ 和 $m$ ，分别表示点和查询的个数。

第二行到第 $n+1$ 行依次输入 $n$ 个点的信息。第 $i+1$ 行（ $1 \leq i \leq n$ ）包含用空格分隔的三项 $x_i,y_i,type_i$ ，分别表示第 $i$ 个点的横、纵坐标和类别，其中坐标为整数、类别为一个大写英文字母 A 或 B。

第 $n+2$ 行到第 $n+m+1$ 行依次输入 $m$ 个查询。第 $j+n+1$ 行（ $1 \leq j \leq m$ ）包含用空格分隔的三个整数 $\theta_0,\theta_1,\theta_2$ ，表示第 $j$ 个查询中给定直线的三个参数。

输出格式

输出到标准输出。

输出共 $m$ 行，每行输出一个字符串。

第 $j$ 行（ $1 \leq j \leq m$ ）输出的字符串对应第 $j$ 个查询的结果：如果给定直线可以完美分隔 A、B 两类点，则输出 Yes；否则输出 No。

input1

output1

1
2
3No
No
Yes

样例 1 解释

只有第 $3$ 个查询给出的直线能将 A、B 两类点完美分隔。

子任务

输入数据保证不存在恰好落在给定直线上的点；
$0 < n \leq 10^{3},\ 0 < m \leq 20$ ，且 A、B 两类点的数量均不为 $0$ ；
所有点的坐标和给定直线的三个参数均为整数，且绝对值 $\leq 10^{4}$ ；
任意两个点的坐标不完全相同。

测试点编号	$\theta_0$	$\theta_1$	$\theta_2$
$1\sim 5$	$\ne 0$	$=0$	$\ne 0$
$6\sim 10$	$\ne 0$	$\ne 0$	$=0$
$11\sim 15$	$=0$	$\ne 0$	$\ne 0$
$16\sim 20$	$\ne 0$	$\ne 0$	$\ne 0$