A Round Peg in a Ground Hole题意 有一个多边形和一个圆，如果多边形不是凸多边形的话输出“HOLE IS ILL-FORMED”；如果圆在多边形内部则输出“PEG WILL FIT”，否则输出“PEG WILL NOT FIT”。思路 先对多边形的顶点极角排序，用叉乘判断多边形是否是凸多边形。然后用叉乘判断圆心是否在多边形内，如果是的话，求出圆心到多边形每条边的距离与半径作比较，进而得出答案。
#pragma GCC optimize(2)
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std
;
typedef long long ll
;
typedef unsigned long ul
;
typedef unsigned long long ull
;
#define pi acos(-1.0)
#define e exp(1.0)
#define pb push_back
#define mk make_pair
#define fir first
#define sec second
#define scf scanf
#define prf printf
typedef pair
<ll
,ll
> pa
;
const int dir_4
[4][2]={-1,0,0,1,1,0,0,-1};
const int dir_8
[8][2]={-1,-1,-1,0,-1,1,0,1,1,1,1,0,1,-1,0,-1};
const ll INF
=0x3f3f3f3f3f3f3f3f;
const int MAX_N
=10000000;
const double eps
=1e-8;
int N
;
struct n_cir
{
double rad
,x
,y
;
}cir
;
struct node
{
double x
,y
;
}pol
[MAX_N
];
double cross_mul(node a
,node b
,node c
){
double x1
,y1
,x2
,y2
;
x1
=b
.x
-a
.x
;
y1
=b
.y
-a
.y
;
x2
=c
.x
-a
.x
;
y2
=c
.y
-a
.y
;
return x1
*y2
-x2
*y1
;
}
double do_dis(node a
,node b
){
return sqrt((a
.x
-b
.x
)*(a
.x
-b
.x
)+(a
.y
-b
.y
)*(a
.y
-b
.y
));
}
double do_hei(node b
,node c
){
return cross_mul(node
{cir
.x
,cir
.y
},b
,c
)/do_dis(b
,c
);
}
bool
cmp(node a
,node b
){
double tmp
=cross_mul(pol
[0],a
,b
);
if(fabs(tmp
)>eps
)
return tmp
>0;
return a
.x
<b
.x
;
}
int main()
{
ios
::sync_with_stdio(false
);
while(cin
>>N
&&N
>=3){
int i
,j
,k
;
cin
>>cir
.rad
>>cir
.x
>>cir
.y
;
for(i
=0;i
<N
;i
++){
cin
>>pol
[i
].x
>>pol
[i
].y
;
}
sort(pol
+1,pol
+N
,cmp
);
bool is_ill
=0,flag
=0,is_nfit
=0,is_nin
=0,flag1
=0;
double pre
,pre1
;
for(i
=0;i
<N
;i
++){
double tmp
=cross_mul(pol
[(i
-1+N
)%N
],pol
[i
],pol
[(i
+1)%N
]);
if(fabs(tmp
)<eps
);
else if(!flag
){
pre
=tmp
;
flag
=1;
}
else if(flag
){
if(pre
*tmp
<0){
is_ill
=1;
}
}
double hei
=do_hei(pol
[i
],pol
[(i
+1)%N
]);
if(hei
<cir
.rad
){
is_nfit
=1;
}
tmp
=cross_mul(node
{cir
.x
,cir
.y
},pol
[i
],pol
[(i
+1)%N
]);
if(fabs(tmp
)<eps
);
else if(!flag1
){
pre1
=tmp
;
flag1
=1;
}
else if(flag1
){
if(tmp
*pre1
<0)
is_nin
=1;
}
}
if(is_ill
)
cout
<<"HOLE IS ILL-FORMED"<<endl
;
else if(is_nfit
||is_nin
)
cout
<<"PEG WILL NOT FIT"<<endl
;
else
cout
<<"PEG WILL FIT"<<endl
;
}
return 0;
}
