题目大意:首先给一个圆的半径和圆心,然后给一个多边形的所有点(多边形按照顺时针或者逆时针给的),求,这个多边形是否是凸多边形,如果是凸多边形在判断这个圆是否在这个凸多边形内。
 
分析:判断凸多边形可以使用相邻的三个点叉积判断,因为不知道顺时针还是逆时针,所以叉积如果有有整数和负数,那么一定不是凸多边形(注意允许多多点在一条线段上)。判断圆在凸多边形首先要判断圆心是否在多边形内,如果在多边形内,再次判断圆心到达到变形每条边的最短距离,如果小于半径就是不合法。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 ;
}

最新文章

  1. 1111MySQL配置参数详解
  2. while:1.兔子生兔子问题 2.打印菱形 3.求100以内质数的和4.洗发水15元一瓶,牙膏5元一支,香皂2元一块,150元刚好花完
  3. 2_STL容器
  4. 【poj1001】 Exponentiation
  5. 项目解析- JspLibrary - part3
  6. 线段树--Color the ball(多次染色问题)
  7. BZOJ 1798: [Ahoi2009]Seq 维护序列seq( 线段树 )
  8. poj1872A Dicey Problem
  9. Python获取秒级时间戳与毫秒级时间戳
  10. win10 UWP 蜘蛛网效果
  11. [WPF]本地化入门
  12. cs231n --- 3 : Convolutional Neural Networks (CNNs / ConvNets)
  13. Intellij Idea配置MapReduce编程环境
  14. python 检测nginx状态,若无法访问发邮件通知
  15. win10 远程出现身份验证错误 要求的函数不受支持
  16. R的常用命令
  17. 【转】cs231n学习笔记-CNN-目标检测、定位、分割
  18. OpenGL chapter5 基础纹理
  19. 在hadoop运行tensor flow
  20. swift -pop的简单动画

热门文章

  1. Fedora 21 中添加及更新源的命令
  2. 关于移动div的具体实现(js)
  3. Node.js(window)基础(1)——用cmd命令行访问某一文件夹下的js文件
  4. favicon.ico的使用方法
  5. php 函数 array_slice
  6. #Leet Code# Same Tree
  7. iOS: plist实例
  8. WPF扩展标记
  9. POJ 1013 Counterfeit Dollar 集合上的位运算
  10. MFC学习指南大纲