CSP 202006-1 线性分类器

原题链接

202006-1 线性分类器

题目分析

题目即给定AB两类点,每次给定一条直线,需要判断这条直线能否将AB两类点完全分开,也就是AB点处于该直线的不同侧。
(知道如何判断点和直线关系的同学可以跳过下面的引用)

关键在于如何判断任意两点关于直线的位置,即在同一侧还是不同侧。
这里注意到直线的表示方式为k_0 + k_1 * x + k_2 * y = 0。若想判断P、Q是否在不同侧,只要把> P、Q的坐标带入直线的方程。
两个结果同号 ——》PQ在直线同一侧
两个结果异号——》PQ在直线不同侧

对于该题满足两个条件的直线就可输出Yes
* A的所有点在同一侧,可以转化为A中的其他点与A的第一个点在同一侧
* A与B的点在不同侧,可以转化为B中的所有点与A的第一个点在不同侧

代码

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

/*判断直线是否能将点分为AB两类
n->点的个数
m->插叙性能的个数
x , y ,type 横纵坐标 + 类别

k1 + k2x + k3y = 0 

可以 Yes
不可以 No
保证不在直线上
数量不为0
任意两点坐标不相同 
*/ 
struct node{
    int x;
    int y;
    node(int x1,int y1){
        x = x1;
        y = y1;
    }
};
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    int x,y,k1,k2,k3;
    string type;
    //输入AB两类点,存储起来 
    vector<node> va,vb;
    for(int i=0;i<n;i++){
        cin>>x>>y>>type;
        if(type == "A")va.push_back(node{x,y});
        else vb.push_back(node{x,y});
    } 
    for(int i=0;i<m;i++){
        cin>>k1>>k2>>k3;//输入一条直线
        bool flag = true;
        //A的所有点在同一侧
        long  t0 = k1 + k2*va[0].x + k3*va[0].y;//第一个点的值 
        for(int j=1;j<va.size();j++){
            long t1 = k1 + k2*va[j].x + k3*va[j].y;
            if((t0>0 && t1<0) || (t0<0 && t1>0)){//存在在不同侧的 
                flag = false;
        //      cout<<"A中存在不同侧的"<<va[j].x<<"\t"<<va[j].y<<endl;
                cout<<"No"<<endl;
                break;
            }
        } 
        if(flag == false) continue;
        //AB在不同侧 
        for(int j=0;j<vb.size();j++){
            long t2 = k1 + k2*vb[j].x + k3*vb[j].y;
            if((t0>0 && t2>0) || (t0<0 && t2<0)){//在同侧 
                flag = false;
        //      cout<<"B中存在与A的点在同侧的"<<vb[j].x<<'\t'<<vb[j].y<<endl;
                cout<<"No"<<endl; 
                break;
            }
        }
        if(flag) cout<<"Yes"<<endl;
    }
    return 0;
} 

Add a Comment

邮箱地址不会被公开。