输入输出样例

样例1

输入

  1. 9 3
  2. 1 1 A
  3. 1 0 A
  4. 1 -1 A
  5. 2 2 B
  6. 2 3 B
  7. 0 1 A
  8. 3 1 B
  9. 1 3 B
  10. 2 0 A
  11. 0 2 -3
  12. -3 0 2
  13. -3 1 1

输出

  1. No
  2. No
  3. Yes

题解

将点的x，y坐标带入直线方程左侧式子，根据结果的正负可以知道该点在直线的上方还是下方。因此如果全部的A类点的计算结果有相同的正负性，B类点也有相同的正负性，且A类点和B类点正负性相反，说明该条直线满足条件。

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scanner = new Scanner(System.in);
  6.         int pointNum = scanner.nextInt();
  7.         int lineNum = scanner.nextInt();
  8.         List<Point> points = new ArrayList<>(pointNum);
  9.         int x, y;
  10.         char type;
  11.         for (int i = 0; i < pointNum; ++i) {
  12.             x = scanner.nextInt();
  13.             y = scanner.nextInt();
  14.             type = scanner.nextLine().charAt(1);
  15.             Point temp = new Point(x, y, type);
  16.             points.add(temp);
  17.         }
  18.         for (int i = 0; i < lineNum; ++i) {
  19.             int[] params = new int[3];
  20.             for (int j = 0; j < 3; ++j) {
  21.                 params[j] = scanner.nextInt();
  22.             }
  24.             boolean ans = true;
  25.             int flagA = 0;
  26.             int flagB = 0;
  27.             int sum;
  28.             for (Point p : points) {
  29.                 sum = params[0] + p.x * params[1] + p.y * params[2];
  30.                 if (p.type == 'A') {
  31.                     if (flagA == 0) {
  32.                         if (sum < 0) {
  33.                             flagA = -1;
  34.                         } else {
  35.                             flagA = 1;
  36.                         }
  37.                     }
  38.                     if (flagA * sum < 0) {
  39.                         ans = false;
  40.                         break;
  41.                     }
  42.                 } else {
  43.                     if (flagB == 0) {
  44.                         if (sum < 0) {
  45.                             flagB = -1;
  46.                         } else {
  47.                             flagB = 1;
  48.                         }
  49.                     }
  50.                     if (flagB * sum < 0) {
  51.                         ans = false;
  52.                         break;
  53.                     }
  54.                 }
  55.                 if (flagA * flagB > 0) {
  56.                     ans = false;
  57.                     break;
  58.                 }
  59.             }
  60.             if (ans) {
  61.                 System.out.println("Yes");
  62.             } else {
  63.                 System.out.println("No");
  64.             }
  65.             if (scanner.hasNextLine()) {
  66.                 scanner.nextLine();
  67.             }
  68.         }
  69.     }
  70. }
  72. class Point {
  73.     public int x;
  74.     public int y;
  75.     public char type;
  77.     public Point(int x, int y, char type) {
  78.         this.x = x;
  79.         this.y = y;
  80.         this.type = type;
  81.     }
  83.     @Override
  84.     public String toString() {
  85.         return "Point [x=" + x + ", y=" + y + ", type=" + type + "]";
  86.     }
  87. }