Blog of DengFeng
0%

CCF一---202006

发表于 更新于 分类于 Valine：
本文字数： 1.9k 阅读时长 ≈ 2 分钟

线性分类器

​ 思路：读完题目发现，是有关直线和点的分布问题，所以首先想到将点代入原直线方程，如果得到的结果大于0，那么这个点就在直线的上方，反之在下方，按照这个思路，就可以去写代码了。

​ 数据结构：考虑到每个点有x坐标（int）、y坐标（int）和类型（String），集合以及数组都不是很好存放point的数据，所以我这里使用Node类存储每个point，然后使用List类型来存放所有的点，使用一个二位数组存放直线的z、x以及y。

1
2
3
4
5
static class Node{
        int x;
        int y;
        String type;
    }

​ 初始化用来存储的过程就不用多说，最主要的思路就在于如果计算，因为在原输入中已经给出了是‘A’类型还是‘B’类型，所以在计算之后要判断一下，并且设置一个总的标记flag，和两个A、B的标记flagA、flagB。只要不满足要求（当有两个同类型的点不在同一边）flag就设为false，结束循环，如果满足就一直进行下去，最后，如果flag为true，仍要判断flagA和flagB是否相等，如果相等，仍然不满足要求，输出No。

以下就是我写的代码（测试为100分）:

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
60
61
62
63
64
65
66
67
68
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    static class Node{
        int x;
        int y;
        String type;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        List<Node> points = new ArrayList<>();
        // 初始化所有的点的集合
        for(int i = 0 ; i < n ; i++){
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            String type = scanner.next();
            Node node = new Node();
            node.x = x;
            node.y = y;
            node.type = type;
            points.add(node);
        }
        int [][] line = new int[m][3];
        for(int i = 0 ; i < m ; i++){
            line[i][0] = scanner.nextInt();
            line[i][1] = scanner.nextInt();
            line[i][2] = scanner.nextInt();
        }
        for(int i = 0 ; i < m ; i++){
            boolean flag = true;
            int flagA = -1 , flagB = -1;
            int z = line[i][0];
            int x = line[i][1];
            int y = line[i][2];
            for(int j = 0 ; j < n ; j++){
                Node node = points.get(j);
                // 大于零说明在这条直线上方
                int t = (z + node.x*x + node.y*y) > 0 ? 1: 0;
                if(node.type.equals("A") ){
                    if(flagA == -1){
                        // 初始化A类的flag
                        flagA = t;
                    }else if (flagA != t){
                        flag = false;
                        break;
                    }
                }else if (node.type.equals("B")){
                    if (flagB == -1){
                        flagB = t;
                    }else if(flagB != t){
                        flag = false;
                        break;
                    }
                }
            }
            if(flag && flagA != flagB){
                System.out.println("Yes");
            }else {
                System.out.println("No");
            }
        }
    }
}