算法提高：计算几何基础｜详解凸包问题-云社区-华为云

点集Q的凸包(convex hull)是指一个最小凸多边形，满足Q中的点或者在多边形边上，或者在其内。图1中由线段表示的多边形就是点集Q={P0,P1,P2,P3,P4,P5,P6}的凸包。

■ 图1 点集的凸包

01、实例应用：捕野猪

问题描述:

由于马克的家在未开发的原始森林，因此野生动物很多。春节前，马克和村民商谈决定大家一起捕野猪，将其作为年猪。捕野猪的方法很简单: 去捕野猪的人一人站一个地方。他们抓住同一根绳子，将一大片森林围起来。只要野猪在里面，就跑不掉。（围成的多边形是简单多边形）

输入:

先输入一个正整数t，表示有t组数据。然后输入一个正整数n，表示有n个人。接下来n行每行有两个整数，表示一个人的位置（顺序是沿着绳子向一个方向输入）。最后一行有两个整数，表示野猪的位置。

输出:

输出是否野猪被捕。若是，则输出yes，否则输出no。

输入样例:

输出样例:

yes

解题思路:

根据给定的点构造一个最小凸边形，然后判断野猪的位置与凸包的关系，确定是在凸包内，还是在凸包外。

判断点是不是在凸包中，以点P为端点，向右边做一条射线，由于多边形是有界的，所以设L一定与多边形相交，当交点数为基数时，P点在多边形内，否则P点在多边形外。其中特殊情况为: L与多边形的顶点相交，当顶点的两相邻边在射线的同侧时，该顶点不算，否则算一个;当射线与一条边重合时，这条边不算，进行逐条线段的扫描。

参考程序: