8.14联想(算法岗)-三语言题解

🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 编程一对一辅导

✨ 本系列打算持续跟新 春秋招笔试题

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

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

🍒 本专栏已收集 60+ 套笔试题,笔试真题 会在第一时间跟新

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

alt

🌰 联想笔试,他来咯

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

剩余60%内容,订阅专栏后可继续查看/也可单篇购买

学长刷题笔记 文章被收录于专栏

这里收集了超全的刷题笔记,欢迎大家的订阅,会持续跟新的

全部评论
第一题我用的cos,不用算叉积,但要算模长,涉及平方根。按那个系统上面的我只过了18%,搞不清楚该咋优化了。另一题我也只过了18%,觉得太巧合了,不知道是不是系统有问题。
点赞 回复 分享
发布于 11-11 12:20 四川

相关推荐

4 26 评论
分享
牛客网
牛客企业服务