poj1584 A Round Peg in a Ground Hole 凸多边形判断 和多边形与圆的位置

//poj1584
//题意：给出一系列的点，给出一个圆，判断这些点按一定方向能否构成凸多边形，
//若是凸多边形，看这个圆是否在多边形内。

//解题思路:
//1. 凸多边形的判断：
//分别用0,1,2来表示叉积的值为零，正，负。对每相邻的三个点进行叉乘，
//而相邻的两个叉乘的值不能异号（根据叉乘可判断出第二个向量在第一个向量的顺时针或逆时针方向），
// 当遍历完所有相邻的三点时没有出来异号那就是凸多边形了。
//附：若有要求相邻边不共线的话就多一个叉值不为0的判断就可以了。

//2.判断圆心是否在凸多边形内，根据上面相同的道理，判断圆心是否在边的同一侧。

//3.判断点到直线的距离（本是点到线段的，但已经确定是凸多边形就不需要了）,利用公式即可。

//代码如下：

#include<iostream>#include<cstdio>#include<math.h>#define eps 1e-8#define _sign(x) (x>eps ? 1: x<-eps ? 2:0)struct Point{double x,y;};struct Line{double a,b,c;};struct Circle{double r;Point center;};double xmult(Point p1,Point p2,Point p0){return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}//凸多边形的判断int isConvex(int n,Point *p){int i,s[3]={1,1,1};for(i=0;i<n && s[1]|s[2];i++)s[_sign(xmult(p[(i+1)%n],p[(i+2)%n],p[i]))]=0;return s[1]|s[2];}//判断点在凸多边形内int insideConvex(Point q,int n,Point *p){int i,s[3]={1,1,1};for(i=0;i<n && s[1]|s[2];i++)s[_sign(xmult(p[(i+1)%n],q,p[i]))]=0;return s[1]|s[2];}//点到直线距离double poToLine(Point p,Line l){return fabs(l.a*p.x+l.b*p.y+l.c)/sqrt(l.a*l.a+l.b*l.b);}//两点成线Line twoPoLine(Point p1,Point p2){Line l;l.a=p1.y-p2.y;l.b=p2.x-p1.x;l.c=p1.x*p2.y-p2.x*p1.y;return l;}Point p[10000];int main(){int n;Circle c;while(scanf("%d",&n),n>2){int i;scanf("%lf%lf%lf",&c.r,&c.center.x,&c.center.y);for(i=0;i<n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);if(isConvex(n,p)){if(insideConvex(c.center,n,p)){for(i=0;i<n;i++){Line l=twoPoLine(p[i],p[(i+1)%n]);if(poToLine(c.center,l)-c.r<0.0){printf("PEG WILL NOT FIT\n");break;}}if(i==n)printf("PEG WILL FIT\n");}elseprintf("PEG WILL NOT FIT\n");}else printf("HOLE IS ILL-FORMED\n");}return 0;}