上门做美容的网站,专业的建站公司推广,wordpress底部导航栏修改,粤信签微信小程序是什么面试算法编程题记录 题目 : 羊圈里的狼 题目背景 : 一到了晚上#xff0c;草原牧民的羊就会被赶进羊圈里。这时#xff0c;野外的狼群就会打羊羔的主意。为了保护羊羔#xff0c;牧民需要将羊圈里的狼赶走或杀死。由于来的狼很多#xff0c;他需要快速甄别哪些狼在羊圈里面… 面试算法编程题记录 题目 : 羊圈里的狼 题目背景 : 一到了晚上草原牧民的羊就会被赶进羊圈里。这时野外的狼群就会打羊羔的主意。为了保护羊羔牧民需要将羊圈里的狼赶走或杀死。由于来的狼很多他需要快速甄别哪些狼在羊圈里面哪些狼在羊圈外面。请写一个程序帮助他。 描述 : 羊圈由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 vectorstruct Point {double x;double y;
};
bool isInsideCircle(const std::vectorPoint 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::vectorPoint 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;
}
