CCF-CSP第19次认证第一题——线性分类器【NA】

CCF-CSP第19次认证第一题——线性分类器

官网题目链接

时间限制： 1.0 秒

空间限制： 512 MiB

下载题目目录（样例文件）

题目描述

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

训练数据包含 𝑛n 个点，其中第 𝑖i 个点（1≤𝑖≤𝑛1≤i≤n）可以表示为一个三元组 (𝑥𝑖,𝑦𝑖,𝑡𝑦𝑝𝑒𝑖)(xi​,yi​,typei​)，即该点的横坐标、纵坐标和类别。

在二维平面上，任意一条直线可以表示为 𝜃0+𝜃1𝑥+𝜃2𝑦=0θ0​+θ1​x+θ2​y=0 的形式，即由 𝜃0θ0​、𝜃1θ1​ 和 𝜃2θ2​ 三个参数确定该直线，且满足 𝜃1θ1​、𝜃2θ2​ 不同时为 00。

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

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

输入格式

从标准输入读入数据。

输入共 𝑛+𝑚+1n+m+1 行。

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

第二行到第 𝑛+1n+1 行依次输入 𝑛n 个点的信息。第 𝑖+1i+1 行（1≤𝑖≤𝑛1≤i≤n）包含用空格分隔的三项 𝑥𝑖xi​、𝑦𝑖yi​ 和 𝑡𝑦𝑝𝑒𝑖typei​，分别表示第 𝑖i 个点的横、纵坐标和类别，其中坐标为整数、类别为一个大写英文字母 A 或 B。

第 𝑛+2n+2 行到第 𝑛+𝑚+1n+m+1 行依次输入 𝑚m 个查询。第 𝑗+𝑛+1j+n+1 行（1≤𝑗≤𝑚1≤j≤m）包含用空格分隔的三个整数 𝜃0θ0​、𝜃1θ1​ 和 𝜃2θ2​，表示第 𝑗j 个查询中给定直线的三个参数。

输出格式

输出到标准输出。

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

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

样例1输入 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

样例1输出 No No Yes

样例1解释

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

子任务

输入数据保证不存在恰好落在给定直线上的点；

0<𝑛≤1030<n≤103、0<𝑚≤200<m≤20，且 A、B 两类点的数量均不为 00；

所有点的坐标和给定直线的三个参数均为整数，且绝对值 ≤104≤104；

任意两个点的坐标不完全相同。

参考题解 #include <iostream> #include <vector> using namespace std; struct Point { int x, y; char type; //A/B }; //struct Line { // int theta0, theta1, theta2; //};没必要，多余的开销 int main () { int n, m; cin >> n >> m; vector<Point> points (n); for (int i = 0; i < n; i++) { //可优化为一句：cin >> points[i].x >> points[i].y >> points[i].type; int x, y; char type; cin >> x >> y >> type; points[i] = {x, y, type}; } for (int i = 0; i < m; i++) { int theta0, theta1, theta2; cin >> theta0 >> theta1 >> theta2; int a_sign = 0; //记录A类点的标号 int b_sign = 0; //记录B类点的标号 bool valid = true; //标记当前查询是否有效 for (auto point : points) { int result = theta0 + theta1 * point.x + theta2 * point.y; if(a_sign == 0 && point.type == 'A') { a_sign = result > 0 ? 1 : -1; } else if (b_sign == 0 && point.type == 'B'){ b_sign = result > 0 ? 1 : -1; } if(point.type == 'A') { if((result < 0 && a_sign == 1) || (result > 0 && a_sign == -1)) { valid = false; break; } } if(point.type == 'B') { if((result < 0 && b_sign == 1) || (result > 0 && b_sign == -1)) { valid = false; break; } } } if (valid && a_sign * b_sign < 0) { //！！！注意要判断AB是否符合相反 cout << "Yes" << "\n"; }else { cout << "No" << "\n"; } } return 0; }

优化版 #include <iostream> #include <vector> using namespace std; struct Point { int x, y; char type; //A/B }; int main () { int n, m; cin >> n >> m; vector<Point> points (n); for (int i = 0; i < n; i++) { cin >> points[i].x >> points[i].y >> points[i].type; } for (int i = 0; i < m; i++) { int theta0, theta1, theta2; cin >> theta0 >> theta1 >> theta2; int a_sign = 0; //记录A类点的标号 int b_sign = 0; //记录B类点的标号 bool valid = true; //标记当前查询是否有效 for (auto point : points) { int result = theta0 + theta1 * point.x + theta2 * point.y; int sign = result > 0 ? 1 : -1; //把判断分开，一个if只进行一个判断，代码更简单了 if(point.type == 'A') { if(a_sign == 0) { a_sign = sign; }else if(sign != a_sign) { valid = false; break; } } else if (point.type == 'B'){ if(b_sign == 0) { b_sign = sign; }else if(sign != b_sign) { valid = false; break; } } } if (valid && a_sign * b_sign < 0) { //！！！注意要判断AB是否符合相反 cout << "Yes\n"; }else { cout << "No\n"; } } return 0; } 总结 要知道直线是如何将平面划分为两部分的：注意只判断相同类别的点在一侧还不够，还要判断是不是AB在不同的一侧