8.14联想(算法岗)-三语言题解
🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试
💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 编程一对一辅导
✨ 本系列打算持续跟新
春秋招笔试题
👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸
✨ 笔试合集传送们 -> 🧷春秋招笔试合集
🍒 本专栏已收集
60+
套笔试题,笔试真题
会在第一时间跟新🍹 感谢各位朋友们的订阅,你们的支持是我们创作的最大动力 💞!
🌰 联想笔试,他来咯
1️⃣ 非常简单的计算几何
2️⃣ 比较经典的DP问题,如果DP比较熟悉的小伙伴,应该可以秒
🌈 01.星际防御系统
问题描述
LYA 是一名星际防御系统的操作员。她负责操控一种高能激光防御装置,用于保护星际基地免受外星生物的入侵。这个防御系统位于一个二维平面上,可以发射直线激光束。
系统检测到 个外星生物,第 个外星生物的位置为 。LYA 每次可以选择一个激光发射点 和一个目标点 ,激光会从发射点沿着直线方向无限延伸。
激光会消灭所有位于激光发射点或激光路径上的外星生物。由于能源限制,LYA 需要在发射前精确计算出一次激光发射能消灭多少个外星生物。你能帮助她完成这个计算吗?
输入格式
第一行包含一个整数 ,表示外星生物的数量。
第二行包含 个整数,依次为 ,表示每个外星生物的坐标。
第三行包含 4 个整数 ,分别表示激光发射点的坐标 和目标点的坐标 。
输出格式
输出一行,包含一个整数,表示此次激光发射能消灭的外星生物数量。
样例输入
3
0 2 2 3 -1 4
1 0 0 2
样例输出
2
数据范围
对于 100% 的数据,满足:
- 保证
题解
这道题目的核心是判断点是否在射线上。我们可以通过向量的叉积和点积来解决这个问题。
-
首先,我们将激光发射方向视为向量 。
-
对于每个外星生物的位置 ,我们计算向量 。
-
判断点是否在射线上需要满足两个条件: a) 和 共线:可以通过判断叉积是否为零来确定。 b) 点在射线的正方向上:可以通过判断点积是否非负来确定。
-
叉积为零且点积非负的点就是在射线上的点。
-
遍历所有点,统计满足条件的点的数量即为答案。
需要注意的是,由于坐标范围较大,计算叉积和点积时可能会溢出,需要用 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%内容,订阅专栏后可继续查看/也可单篇购买
这里收集了超全的刷题笔记,欢迎大家的订阅,会持续跟新的