面試算法編程題記錄

題目 : 羊圈里的狼
題目背景 :
一到了晚上，草原牧民的羊就會被趕進羊圈里。這時，野外的狼群就會打羊羔的主意。為了保護羊羔，牧民需要將羊圈里的狼趕走或殺死。由于來的狼很多，他需要快速甄別哪些狼在羊圈里面，哪些狼在羊圈外面。請寫一個程序幫助他。
描述 :
羊圈由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;
}