在线等，急求一道C语言的编程题！！！正确答案直接发20元微信红包

凸包问题。计算几何。

#include
#include
struct node
{
    long long x,y;
}a[100005],b[100005];
long long mul(node p1,node p2,node p3)
{
    return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
}
int main()
{
    int n,m,i,low,high,mid,flag;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i            scanf("%lld%lld",&a[i].x,&a[i].y);
        scanf("%d",&m);
        for(i=0;i            scanf("%lld%lld",&b[i].x,&b[i].y);
        flag=0;
        for(i=0;i        {
            if(mul(a[0],a[1],b[i])>=0||mul(a[0],a[n-1],b[i])<=0)
            {
                flag=1;
                goto loop;
            }
            low=2;  high=n-1;
            while(low            {
                mid=(low+high)>>1;
                if(mul(a[0],a[mid],b[i])>0)
                    high=mid;
                else low=mid+1;
            }
            if(mul(a[low],a[low-1],b[i])<=0)
            {
                flag=1;
                goto loop;
            }
        }
loop:    if(flag)
            printf("NO\n");
         else printf("YES\n");
    }
    return 0;
}

转自http://www.cnblogs.com/dream-wind/archive/2012/05/23/2514694.html

算法描述里面也有。

排序，先按照x坐标排序，找出x最大、最小两点（左右最边点）。连接这两点，其他各点，按纵坐标分组，纵坐标在该线上方的归一组，该线下方的归一组。两组中的点，一组在下边，一组在上边。按横坐标，是相邻的点。这样点可以任意输。
上方的点，在左右邻居连线的上方为凸，下方非凸；下方的点，位于左右邻居连线的下方为凸，上方非凸。
判断内外：根据x值，找出该点左右相邻的下边、上边两点，y值如果位于上下个两点的连线之间（包括线上），就是在内部，否则在外部。

计算原理：
（1）是否为凸多边形：前三个点计算三角形（封闭线的面积，用积分方式计算），以后每加一个点面积均应增加或至少相等。
（2）最后一个点是否在凸多边形内：同上方式计算加上这个点的多边形的面积，相等或减少表示在内 ！