面试算法编程题

面试算法编程题记录

题目 : 羊圈里的狼
题目背景 :
一到了晚上，草原牧民的羊就会被赶进羊圈里。这时，野外的狼群就会打羊羔的主意。为了保护羊羔，牧民需要将羊圈里的狼赶走或杀死。由于来的狼很多，他需要快速甄别哪些狼在羊圈里面，哪些狼在羊圈外面。请写一个程序帮助他。
描述 :
羊圈由n 个连续点组成{ Pi }, 1 <= i <= n; 3 <= n <= 100.其中, P1与Pn首尾相连，形成一个闭合的羊圈。假设狼的位置为(x, y)，且保证该点不在墙上，需要判断其在圈里还是圈外。
输入格式
输入第一行，一个正整数 n(3 <= n <= 100)表示圈坐标点的个数。接下来输入n行，每行两个浮点数代表羊圈的坐标点 Pi;
输入多行数据，每行数据两个浮点数(x, y)，表示该条狼的位置。
输出格式 :
输出多行数据，每行数据为一个字符串，表示该条狼是否在羊圈里。如果在里面输出True，否则输出 False。

#include <iostream>
#include <vector>struct Point {double x;double y;
};
bool isInsideCircle(const std::vector<Point>& circle, const Point& wolf) {int crossCount = 0;for (int i = 0; i < circle.size(); ++i) {const Point& p1 = circle[i];//先后两个点const Point& p2 = circle[(i + 1) % circle.size()];if ((p1.y > wolf.y) != (p2.y > wolf.y) &&wolf.x < (p2.x - p1.x) * (wolf.y - p1.y) / (p2.y - p1.y) + p1.x) {++crossCount;}}return crossCount % 2 == 1;
}
int main() {int n;std::cin >> n;std::vector<Point> circle(n);for (int i = 0; i < n; ++i) {std::cin >> circle[i].x >> circle[i].y;}int m;std::cin >> m;for (int i = 0; i < m; ++i) {Point wolf;std::cin >> wolf.x >> wolf.y;std::cout << (isInsideCircle(circle, wolf) ? "True" : "False") << std::endl;}return 0;
}