💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

1️⃣ 非常简单的计算几何

2️⃣ 比较经典的DP问题，如果DP比较熟悉的小伙伴，应该可以秒

🌈 01.星际防御系统

问题描述

LYA 是一名星际防御系统的操作员。她负责操控一种高能激光防御装置，用于保护星际基地免受外星生物的入侵。这个防御系统位于一个二维平面上，可以发射直线激光束。

系统检测到 个外星生物，第 个外星生物的位置为 。LYA 每次可以选择一个激光发射点 和一个目标点 ，激光会从发射点沿着直线方向无限延伸。

激光会消灭所有位于激光发射点或激光路径上的外星生物。由于能源限制，LYA 需要在发射前精确计算出一次激光发射能消灭多少个外星生物。你能帮助她完成这个计算吗？

输入格式

第一行包含一个整数 ，表示外星生物的数量。

第二行包含 个整数，依次为 ，表示每个外星生物的坐标。

第三行包含 4 个整数 ，分别表示激光发射点的坐标 和目标点的坐标 。

输出格式

输出一行，包含一个整数，表示此次激光发射能消灭的外星生物数量。

样例输入

3
0 2 2 3 -1 4
1 0 0 2

样例输出

2

数据范围

对于 100% 的数据，满足：

• 
• 
• 保证

题解

这道题目的核心是判断点是否在射线上。我们可以通过向量的叉积和点积来解决这个问题。

1. 首先，我们将激光发射方向视为向量 。

2. 对于每个外星生物的位置 ，我们计算向量 。

3. 判断点是否在射线上需要满足两个条件： a) 和 共线：可以通过判断叉积是否为零来确定。 b) 点在射线的正方向上：可以通过判断点积是否非负来确定。

4. 叉积为零且点积非负的点就是在射线上的点。

5. 遍历所有点，统计满足条件的点的数量即为答案。

需要注意的是，由于坐标范围较大，计算叉积和点积时可能会溢出，需要用 long long 来存储中间结果。

时间复杂度：，其中 是外星生物的数量。 空间复杂度：，用于存储外星生物的坐标。

参考代码

• Python

def on_ray(x1, y1, x2, y2, px, py):
    """
    判断点 (px, py) 是否在从 (x1, y1) 到 (x2, y2) 的射线上
    """
    vx1, vy1 = x2 - x1, y2 - y1
    vx2, vy2 = px - x1, py - y1
    
    # 计算叉积
    cross = vx1 * vy2 - vy1 * vx2
    if cross != 0:
        return False
    
    # 计算点积
    dot = vx1 * vx2 + vy1 * vy2
    return dot >= 0

# 读取输入
n = int(input())
coords = list(map(int, input().split()))
x, y, x2, y2 = map(int, input().split())

# 统计在射线上的点的数量
count = 0
for i in range(0, 2*n, 2):
    if on_ray(x, y, x2, y2, coords[i], coords[i+1]):
        count += 1

# 输出结果
print(count)

• Java

import java.util.Scanner;

public class Main {
    // 判断点 (px, py) 是否在从 (x1, y1) 到 (x2, y2) 的射线上
    static boolean onRay(int x1, int y1, int x2, int y2, int px, int py) {
        long vx1 = x2 - x1, vy1 = y2 - y1;
        long vx2 = px - x1, vy2 = py - y1;
        
        // 计算叉积
        long cross = vx1 * vy2 - vy1 * vx2;
        if (cross != 0) return false;
        
        // 计算点积
        long dot = vx1 * vx2 + vy1 * vy2;
        return dot >= 0;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int n = scanner.nextInt();
        int[] coords = new int[2*n];
        for (int i = 0; i < 2*n; i++) {
            coords[i] = scanner.nextInt();
        }
        int x = scanner.nextInt();
        int y = scanner.nextInt();
        int x2 = scanner.nextInt();
        int y2 = scanner.nextInt();
        
        // 统计在射线上的点的数量
        int count = 0;
        for (int i = 0; i < 2*n; i += 2) {
            if (onRay(x, y, x2, y2, coords[i], coords[i+1])) {
                count++;
            }
        }
        
        // 输出结果
        System.out.println(count);
        
        scanner.close();
    }
}

• Cpp

#include <iostream>
#include <vector>

using namespace std;

typedef long long LL;

// 判断点 (px, py) 是否在从 (x1, y1)