题目链接:https://vjudge.net/problem/POJ-1584

题意:首先要判断凸包,然后判断圆是否在多边形中。

思路:
  判断凸包利用叉积,判断圆在多边形首先要判断圆心是否在多边形中,然后判断圆心到每条边的距离是否小于半径。板子很重要!!

AC code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std; const double eps=1e-;
const double inf=1e20;int sgn(double x){
if(abs(x)<eps) return ;
if(x<) return -;
return ;
} struct Point{
double x,y;
Point(){}
Point(double xx,double yy):x(xx),y(yy){}
Point operator + (const Point& b)const{
return Point(x+b.x,y+b.y);
}
Point operator - (const Point& b)const{
return Point(x-b.x,y-b.y);
}
double operator * (const Point& b)const{
return x*b.x+y*b.y;
}
double operator ^ (const Point& b)const{
return x*b.y-b.x*y;
}
//绕原点旋转角度b(弧度值),后x、y的变化
void transXY(double b){
double tx=x,ty=y;
x=tx*cos(b)-ty*sin(b);
y=tx*sin(b)+ty*cos(b);
}
}; struct Line{
Point s,e;
Line(){}
Line(Point ss,Point ee){
s=ss,e=ee;
}
//两直线相交求交点
//第一个值为0表示直线重合,为1表示平行,为2表示相交
//只有第一个值为2时,交点才有意义
pair<int,Point> operator &(const Line &b)const{
Point res = s;
if(sgn((s-e)^(b.s-b.e)) == )
{
if(sgn((s-b.e)^(b.s-b.e)) == )
return make_pair(,res);//重合
else return make_pair(,res);//平行
}
double t = ((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e));
res.x += (e.x-s.x)*t;
res.y += (e.y-s.y)*t;
return make_pair(,res);
}
};
//判断线段相交
bool inter(Line l1,Line l2){
return
max(l1.s.x,l1.e.x)>=min(l2.s.x,l2.e.x)&&
max(l2.s.x,l2.e.x)>=min(l1.s.x,l1.e.x)&&
max(l1.s.y,l1.e.y)>=min(l2.s.y,l2.e.y)&&
max(l2.s.y,l2.e.y)>=min(l1.s.y,l1.e.y)&&
sgn((l1.s-l2.s)^(l2.e-l2.s))*sgn((l1.e-l2.s)^(l2.e-l2.s))<=&&
sgn((l2.s-l1.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s))<=;
} double dis(Point a,Point b){
return sqrt((b-a)*(b-a));
}
//判断点在线段上
bool OnSeg(Point P,Line L){
return
sgn((L.s-P)^(L.e-P))==&&
sgn((P.x-L.s.x)*(P.x-L.e.x))<=&&
sgn((P.y-L.s.y)*(P.y-L.e.y))<=;
}
//判断点在凸多边形内,复杂度O(n)
//点形成一个凸包,而且按逆时针排序(如果是顺时针把里面的<0改为>0)
//点的编号:0~n-1
//返回值:
//-1:点在凸多边形外
//0:点在凸多边形边界上
//1:点在凸多边形内
int inConvexPoly(Point a,Point p[],int n){
for(int i=;i<n;++i)
if(sgn((p[i]-a)^(p[(i+)%n]-a))<) return -;
else if(OnSeg(a,Line(p[i],p[(i+)%n]))) return ;
return ;
}
//判断点在任意多边形内,复杂度O(n)
//射线法,poly[]的顶点数要大于等于3,点的编号0~n-1,按逆时针或顺时针排序
//返回值
//-1:点在凸多边形外
//0:点在凸多边形边界上
//1:点在凸多边形内
int inPoly(Point a,Point p[],int n){
int cnt=;
Line ray,side;
ray.s=a;
ray.e.y=a.y;
ray.e.x=-inf;
for(int i=;i<n;++i){
side.s=p[i];
side.e=p[(i+)%n];
if(OnSeg(a,side)) return ;
if(sgn(side.s.y-side.e.y)==) continue;
if(OnSeg(side.s,ray)){
if(sgn(side.s.y-side.e.y)>) ++cnt;
}
else if(OnSeg(side.e,ray)){
if(sgn(side.e.y-side.s.y)>) ++cnt;
}
else if(inter(ray,side)) ++cnt;
}
if(cnt%==) return ;
else return -;
}
//判断凸多边形
//允许共线边
//点可以是顺时针给出也可以是逆时针给出
//点的编号是0~n-1
bool isconvex(Point poly[],int n){
bool s[];
memset(s,false,sizeof(s));
for(int i=;i<n;++i){
s[sgn((poly[(i+)%n]-poly[i])^(poly[(i+)%n]-poly[i]))+]=true;
if(s[]&&s[]) return false;
}
return true;
}
//点到线段的距离
//返回点到线段最近的点
Point NearestPointToLineSeg(Point P,Line L){
Point result;
double t=((P-L.s)*(L.e-L.s))/((L.e-L.s)*(L.e-L.s));
if(t>=&&t<=){
result.x=L.s.x+(L.e.x-L.s.x)*t;
result.y=L.s.y+(L.e.y-L.s.y)*t;
}
else{
if(dis(P,L.s)<dis(P,L.e))
return L.s;
else
return L.e;
}
return result;
} int n;
double R,X,Y;
Point pt[]; int main(){
while(scanf("%d",&n),n>=){
scanf("%lf%lf%lf",&R,&X,&Y);
for(int i=;i<n;++i)
scanf("%lf%lf",&pt[i].x,&pt[i].y);
if(!isconvex(pt,n)){
printf("HOLE IS ILL-FORMED\n");
continue;
}
Point P=Point(X,Y);
if(inPoly(P,pt,n)==-){
printf("PEG WILL NOT FIT\n");
continue;
}
int flag=;
for(int i=;i<n;++i){
if(sgn(dis(P,NearestPointToLineSeg(P,Line(pt[i],pt[(i+)%n])))-R)<){
flag=;
break;
}
}
if(flag) printf("PEG WILL FIT\n");
else printf("PEG WILL NOT FIT\n");
}
return ;
}

最新文章

  1. java学习笔记之泛型
  2. web.Config配置数据库的连接
  3. oom_kill_process造成数据库挂起并出现found dead shared server
  4. Linux学习笔记(12)用户和用户组管理
  5. 微软职位内部推荐-Principal Architect for Windows Security
  6. 更改OS序列号(slmgr)
  7. 【转】JAVA中的浅拷贝和深拷贝
  8. MYSQL delete 从多人表中删除
  9. StringUtils.isNumeric(String str) 的一个坑(转)
  10. html页面高度自适应
  11. 拷贝JAR包
  12. Git常用命令总结(超实用)【转】
  13. Python中list、字典、字符串的讲解
  14. Effective Java 第三版—— 87. 考虑使用自定义序列化形式
  15. 1131(★、※)Subway Map
  16. 左右两栏div布局,高度自适应
  17. Error configuring application listener of class org.springframework.web.context.ContextLoaderListener
  18. .net写入文本到本地
  19. 【校招面试 之 剑指offer】第11题 旋转数组中的最小数字
  20. sql server分配某个用户只对某一个数据库有权限 转载 http://blog.sina.com.cn/s/blog_13554ebc70102wi3h.html

热门文章

  1. vue 的 watch 如何在初始化时执行
  2. 可持久化数据结构(平衡树、trie树、线段树) 总结
  3. PCIe - 周扒皮,扒扒TLP层
  4. CentOS 7 常用命令大全(转)
  5. (转)shell调试方法
  6. shell 脚本同时对远程多台机器执行命令
  7. Tkinter 之RadioButton单选框标签
  8. CodeForces - 1183E Subsequences (easy version) (字符串bfs)
  9. 《基于Python的GMSSL实现》课程设计个人报告
  10. c语言复杂申明解释程序