#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const double zero=1e-8;
const int maxn=1588;
int n;
double r;
bool iszero(double x){return abs(x)<0.0000001;}
struct node
{
	double x,y;
	node(){}
	node(double _x,double _y):x(_x),y(_y){}
	bool operator<(const node &s)const
	{
		if(!iszero(y-s.y))return y<s.y;
		return x<s.x;
	}	
	void read()
	{
		scanf("%lf%lf",&x,&y);
	}
	void write()
	{
		printf("(%.2lf,%.2lf)\n",x,y);
	}
}MAX(1e59,1e107),c,p[maxn];
double cp(node e1,node e2,node b)
{
	return (e1.x-b.x)*(e2.y-b.y)-(e2.x-b.x)*(e1.y-b.y);
}
bool onseg(node p,node p1,node p2)
{
	double lx=min(p1.x,p2.x),rx=max(p1.x,p2.x);
	double ly=min(p1.y,p2.y),ry=max(p1.y,p2.y);
	return (lx<=p.x&&p.x<=rx&&ly<=p.y&&p.y<=ry);
}
bool segtoseg_intersection(node i0,node i1,node j0,node j1)
{
	double t1=cp(j0,i1,i0),t2=cp(j1,i1,i0);
	double t3=cp(i0,j0,j1),t4=cp(i1,j0,j1);
	if(t1*t2<0&&t3*t4<0)return 1;
	if(iszero(t1)&&onseg(j0,i0,i1))return 1;
	return 0;
}
bool linetoline_intersection(node i0,node i1,node j0,node j1)
{
	double t1=cp(j0,i1,i0),t2=cp(j1,i1,i0);
	if(t1*t2<=0)return 1;
	return 0;
}
bool parallel(node p1,node p2,node p3,node p4)
{
	double x12=p2.x-p1.x,x34=p4.x-p3.x;
	if(iszero(x12))return iszero(x34);
	double k1=(p2.y-p1.y)/x12,k2=(p4.y-p3.y)/x34;
	return iszero(k1-k2);
}
node gcp(node p1,node p2,node p3,node p4)
{
	double a1=p1.y-p2.y,b1=p2.x-p1.x,c1=p1.x*p2.y-p2.x*p1.y;
	double a2=p3.y-p4.y,b2=p4.x-p3.x,c2=p3.x*p4.y-p4.x*p3.y;
	double x0=(c1*b2-c2*b1)/(a2*b1-a1*b2);
	double y0=(a2*c1-a1*c2)/(a1*b2-a2*b1);
	return node(x0,y0);
}
double get3area(node p1,node p2,node p3)
{
	return abs(cp(p1,p2,p3)/2);
}
double get4area(node p1,node p2,node p3,node p4)
{
	return get3area(p1,p2,p3)+get3area(p1,p4,p3);
}
double cf(double x){return x*x;}
double dis(node a,node b)
{
	return sqrt(cf(a.x-b.x)+cf(a.y-b.y));
}
bool cc()
{
	int dir=0;
	double temp=0;
	for(int i=0;i<n;++i)
	{
		temp=cp(p[i+2],p[i+1],p[i]);
		//printf("%lf %lf\n")
		if(!dir)dir=temp;
		if(dir*temp<0)return 0;
	}
	return 1;
}
bool PtoE_dis(node x,node a,node b)
{
	return get3area(x,a,b)*2/dis(a,b);
}
bool inpolygon(node x)
{
	int res=0;
	for(int i=0;i<n;++i)
	{
		if(parallel(x,MAX,p[i],p[i+1]))continue;
		if(segtoseg_intersection(x,MAX,p[i],p[i+1]))
			++res;
	}
	return res&1;
}
int main()
{
	//freopen("in.txt","r",stdin);
	while(1)
	{
		scanf("%d%lf",&n,&r);c.read();
		if(n==1)break;
		for(int i=1;i<=n;++i)
			p[i].read();
		p[0]=p[n];p[n+1]=p[1];
		if(!cc())puts("HOLE IS ILL-FORMED");
		else
		{
			bool flag1=1,flag2=1;
			if(!inpolygon(c))flag1=0;
			if(flag1)for(int i=0;i<n;++i)
				if(PtoE_dis(c,p[i],p[i+1])<r)
				{	
					flag2=0;break;
				}
			if(flag1&&flag2)puts("PEG WILL FIT");
			else puts("PEG WILL NOT FIT");
		}
		
	}
}

• Re:ORZ 求nb的测试数据 (76) lazycal 2014-01-20 17:05:54