题目大意：首先给一个圆的半径和圆心，然后给一个多边形的所有点（多边形按照顺时针或者逆时针给的），求，这个多边形是否是凸多边形，如果是凸多边形在判断这个圆是否在这个凸多边形内。
分析：判断凸多边形可以使用相邻的三个点叉积判断，因为不知道顺时针还是逆时针，所以叉积如果有有整数和负数，那么一定不是凸多边形（注意允许多多点在一条线段上）。判断圆在凸多边形首先要判断圆心是否在多边形内，如果在多边形内，再次判断圆心到达到变形每条边的最短距离，如果小于半径就是不合法。ps：一道好题，通过这个题学会了不少东西。
代码如下：
=======================================================================================================================================
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std; const int MAXN = 1e3+;
const double EPS = 1e-;
const double oo = 1e10+; struct Point
{
double x, y;
Point(double x=, double y=):x(x),y(y){}
Point operator - (const Point &tmp)const{
return Point(x-tmp.x, y-tmp.y);
}
double operator ^(const Point &tmp)const{
return x*tmp.y - y*tmp.x;
}
double operator *(const Point &tmp)const{
return x*tmp.x + y*tmp.y;
}
};
double Dist(Point a, Point b)
{///两点间的距离
return sqrt((a-b)*(a-b));
}
int Sign(double t)
{
if(t > EPS)return ;
if(fabs(t) < EPS)return ;
return -;///负数
}
struct Segment
{
Point S, E;
Segment(Point S=, Point E=):S(S), E(E){}
bool OnSeg(const Point &p)
{///点是否在线段上
if(Sign( (S-E)^(p-E) ) == )///共线
if(Sign( (p.x-S.x)*(p.x-E.x) ) <= )///位于线段的中间或者端点
if(Sign( (p.y-S.y)*(p.y-E.y) ) <= )
return true;
return false;
}
bool Inter(const Segment &tmp)
{///只考虑完全相交的情况
return Sign((S-E)^(tmp.S-E)) * Sign((S-E)^(tmp.E-E)) == -;
}
Point NearPoint(const Point &p)
{///点到线段最近的点
Point res;
double r = ((E-S)*(p-S)) / ((E-S)*(E-S)); if(r > EPS && (1.0 - r) > EPS )
{///点在线段的投影在线段上
res.x = S.x + r * (E.x-S.x);
res.y = S.y + r * (E.y-S.y);
}
else
{///求离最近的端点
if(Dist(p, S) < Dist(p, E))
res = S;
else
res = E;
} return res;
}
};
struct Poly
{
int N;
Point vertex[MAXN]; bool IsConvex()
{///判断是否是凸多边形，可以共线
int vis[] = {};
for(int i=; i<N; i++)
{///如果同时出现整数和负数，说明存在凹的
int k = Sign((vertex[(i+)%N]-vertex[i])^(vertex[(i+)%N]-vertex[i]));
vis[k+] = ; if(vis[] && vis[])
return false;
}
return true;
}
int InPoly(const Point &Q)
{///判断点Q是否在多边形内，射线法，奇数在内，偶数在外
///在圆上返回0， 圆外-1， 圆内 1
Segment ray(Point(-oo, Q.y), Q);///构造射线的最远处
int cnt=;///统计相交的边数 for(int i=; i<N; i++)
{
Segment edge(vertex[i], vertex[(i+)%N]); if(edge.OnSeg(Q) == true)
return ;///点在边上 if(ray.OnSeg(vertex[i]) == true)
{///如果相交连接点，那么取y值小的点
if(vertex[(i+)%N].y - vertex[i].y > EPS)
cnt++;
}
else if(ray.OnSeg(vertex[(i+)%N]) == true)
{
if(vertex[i].y - vertex[(i+)%N].y > EPS)
cnt++;
}
else if(ray.Inter(edge) && edge.Inter(ray))
cnt++;
} if(cnt % )
return ;
else
return -;
}
};
struct Circle
{
Point center;///圆心
double R;///半径
}; bool Find(Poly &a, Circle &c)
{///判断圆是否在多边形内
if(a.InPoly(c.center) == -)
return false;///如果圆心在多边形外面 for(int i=; i<a.N; i++)
{
Segment edge(a.vertex[i], a.vertex[(i+)%a.N]);
double len = Dist(c.center, edge.NearPoint(c.center)); if(Sign(len-c.R) < )
return false;
} return true;
} int main()
{
Poly a;///定义多边形
Circle c;///定义圆 while(scanf("%d", &a.N) != EOF && a.N > )
{
scanf("%lf%lf%lf", &c.R, &c.center.x, &c.center.y);
for(int i=; i<a.N; i++)
scanf("%lf%lf", &a.vertex[i].x, &a.vertex[i].y); if(a.IsConvex() == false)
printf("HOLE IS ILL-FORMED\n");
else if(Find(a, c) == false)
printf("PEG WILL NOT FIT\n");
else
printf("PEG WILL FIT\n");
} return ;
}