点集Q的凸包(convex hull)是指一个最小凸多边形，满足Q中的点或者在多边形边上，或者在其内。图1中由线段表示的多边形就是点集Q={P0,P1,P2,P3,P4,P5,P6}的凸包。
■ 图1 点集的凸包
01、实例应用：捕野猪
问题描述:
由于马克的家在未开发的原始森林，因此野生动物很多。春节前，马克和村民商谈决定大家一起捕野猪，将其作为年猪。捕野猪的方法很简单: 去捕野猪的人一人站一个地方。他们抓住同一根绳子，将一大片森林围起来。只要野猪在里面，就跑不掉。（围成的多边形是简单多边形）
输入:
先输入一个正整数t，表示有t组数据。然后输入一个正整数n，表示有n个人。接下来n行每行有两个整数，表示一个人的位置（顺序是沿着绳子向一个方向输入）。最后一行有两个整数，表示野猪的位置。
输出:
输出是否野猪被捕。若是，则输出yes，否则输出no。
输入样例:
1
3
0 0
2 0
0 2
1 1
输出样例:
yes
解题思路:
根据给定的点构造一个最小凸边形，然后判断野猪的位置与凸包的关系，确定是在凸包内，还是在凸包外。
判断点是不是在凸包中，以点P为端点，向右边做一条射线，由于多边形是有界的，所以设L一定与多边形相交，当交点数为基数时，P点在多边形内，否则P点在多边形外。其中特殊情况为: L与多边形的顶点相交，当顶点的两相邻边在射线的同侧时，该顶点不算，否则算一个;当射线与一条边重合时，这条边不算，进行逐条线段的扫描。
参考程序:
