poj1584 A Round Peg in a Ground Hole

发表于 | 更新于

Link

Solution

用叉积判转向判凸多边形 然后是点到直线的距离 和判点在多边形内

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
//Code by Lucida
#include<cstdio>
#include<algorithm>
#include<cmath>
#define red(x) scanf("%d",&x)
#define fred(x) scanf("%lf",&x)
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
typedef double ld;
const ld eps=1e-10;
const int MAXN=1e5;
const char ILL[]="HOLE IS ILL-FORMED",
		   FIT[]="PEG WILL FIT",
		   NOTFIT[]="PEG WILL NOT FIT";
int fcmp(ld x)
{
	if(-eps<x && x<eps) return 0;
	return x<0?-1:1;
}
template <class T> T sqr(T x){return x*x;}
template <class T> T abs(T x){return x>0?x:-x;}
struct vec
{
	ld x,y;
	vec(ld _x=0,ld _y=0):x(_x),y(_y){}
	vec operator -(){return vec(x,y);}
	ld norm(){return sqrt(x*x+y*y);}
};
typedef vec point;
vec operator +(vec u,vec v){return vec(u.x+v.x,u.y+v.y);}
vec operator -(vec u,vec v){return vec(u.x-v.x,u.y-v.y);}
vec operator *(vec u,ld t){return vec(u.x*t,u.y*t);}
vec operator /(vec u,ld t){return vec(u.x/t,u.y/t);}
ld outer(vec u,vec v){return u.x*v.y-u.y*v.x;}
ld inner(vec u,vec v){return u.x*v.x+u.y*v.y;}
struct line
{
	point A;vec v;
	line(point _A,vec _v):A(_A),v(_v){}
};
ld dist(point A,line l)
{
	vec AB=l.A-A,BC=l.v;
	return abs(outer(AB,BC))/BC.norm();
}
struct circle
{
	point O;ld r;
	circle(point _O,ld _r):O(_O),r(_r){}
	
};
bool parl(vec u,vec v){return fcmp(outer(u,v))==0;}
bool on(point A,line l){return parl(A-l.A,l.v);}
int relation(circle C,line l)
{
	ld d=dist(C.O,l);
	return fcmp(d-C.r);
}
int relation(point A,point *p,int n)
{
	#define suc(i) (i+1>n ?1:i+1)
	int wn=0;
	for(int i=1;i<=n;i++)
	{
		if(on(A,line(p[i],p[suc(i)]-p[i]))) return 0;
		if(fcmp(outer(A-p[i],p[suc(i)]-p[i]))>0 && fcmp(A.y-p[i].y)>=0 && fcmp(A.y-p[suc(i)].y)<0) wn++;
		if(fcmp(outer(A-p[i],p[suc(i)]-p[i]))<0 && fcmp(A.y-p[i].y)<0 && fcmp(A.y-p[suc(i)].y)>=0) wn--;
	}
	return wn==0?1:-1;
	#undef suc
}
const char *WORK(int n)
{
	ld r,x,y;fred(r),fred(x),fred(y);
	circle C=circle(point(x,y),r);
	static point p[MAXN];
	for(int i=1;i<=n;i++) fred(p[i].x),fred(p[i].y);
	#define pre(i) (i-1==0?n:i-1)
	#define suc(i) (i+1>n ?1:i+1)
	int dir;
	for(int i=1;i<=n;i++)
	{
		dir=fcmp(outer(p[i]-p[pre(i)],p[suc(i)]-p[i]));
		if(dir) break;
		else if(i==n) return ILL;
	}
	for(int i=2;i<=n;i++)
		if(dir*fcmp(outer(p[i]-p[pre(i)],p[suc(i)]-p[i]))<0) return ILL;
	if(relation(C.O,p,n)>0) return NOTFIT;
	for(int i=1;i<=n;i++)
		if(relation(C,line(p[i],p[suc(i)]-p[i]))<0) return NOTFIT;
	return FIT;
	#undef pre
	#undef suc
}
int main()
{
	freopen("input","r",stdin);
	int n;
	while(red(n) && n>=3)
		printf("%s\n",WORK(n));
	return 0;
}