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;
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2017 Hey,Lucida here. All Rights Reserved.

Lucida Lu 保留所有权利