面试算法编程题

面试算法编程题记录

题目 : 羊圈里的狼

题目背景 :

一到了晚上，草原牧民的羊就会被赶进羊圈里。这时，野外的狼群就会打羊羔的主意。为了保护羊羔，牧民需要将羊圈里的狼赶走或杀死。由于来的狼很多，他需要快速甄别哪些狼在羊圈里面，哪些狼在羊圈外面。请写一个程序帮助他。

描述 :

羊圈由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;
}