【CCF】线性分类器

输入样例：

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           

复制

样例解释：

解题思路：

本质就是计算点到直线的距离（只不过分子不加绝对值），根据距离公式分母恒大于零不必考虑，分子

就是θ₀+θ₁x+θ₂y，如果为正说明在上方，如果为负说明在另一侧。

100分代码：

#include <bits/stdc++.h>
using namespace std;

struct node
{
    int x,y;   //横、纵坐标
    char type; //类别
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    vector<node> v;
    int n,m;
    cin >> n >> m;  //点和查询个数
    for(int i=1; i<=n; i++) {
        node _;
        cin >> _.x >> _.y >> _.type;
        v.push_back(_);
    }
    for(int i=1; i<=m; i++) {
        int a,b,c;
        cin >> a >> b >> c;
        bool flag = true;
        int flagA = -1, flagB = -1;
        for(int j=0; j<n; j++) {
            int t = (a+b*v[j].x+c*v[j].y>0)?1:0; //1直线上方,0直线下方
            if(v[j].type=='A') { 
                if(flagA==-1)  
                    flagA = t;  //初始化在直线的哪一段
                else if(flagA!=t) {
                    flag = false;
                    break;
                }
            } else if(v[j].type=='B') {
                if(flagB==-1)
                    flagB = t;  //初始化在直线的哪一段
                else if(flagB!=t) {
                    flag = false;
                    break;
                }
            }
        }
        cout << (flag?"Yes":"No") << endl;
    }
    return 0;
}           

复制