POJ1584:A Round Peg in a Ground Hole(叉积,凸包) - c++编程基础

=0;
for(i=0;i {
if(cw(a[i],a[i+1],a[(i+2)%n])!=0)
{
if(dirt==0)
dirt=cw(a[i],a[i+1],a[(i+2)%n]);
else if(cw(a[i],a[i+1],a[(i+2)%n])>0&&dirt<0
||cw(a[i],a[i+1],a[(i+2)%n])<0&&dirt>0)
{
flag=false;
break;
}
}
}
if(flag==false)
{
printf("HOLE IS ILL-FORMED\n");
continue;
}
for(i=0;i {
double d=dist(a[i],a[(i+1)%n],center);
double res=cw(a[i],a[(i+1)%n],center);
if(d0
||res>0&&dirt<0||res==0)
{
flag=false;
break;
}
}
if(!flag)
{
printf("PEG WILL NOT FIT\n");
}
else
printf("PEG WILL FIT\n");
}
}

首先要判断多边形是否凸包.

由于题目是按照顺时针或逆时针方向给出所有点,所以不需要对所有点进行排序

使用叉积判断凸包

允许多点共线情况的存在

陷阱是:

圆心可能不在多边形内部

要求出圆心到多边形各边的距离,所有边的距离都要大于半径

求点到线段的距离的方法:利用叉积

POJ1584:A Round Peg in a Ground Hole(叉积,凸包)(二)