题目链接:http://lightoj.com/volume_showproblem.php?problem=1190

题意:给你一个多边形含有n个点;然后又m个查询,每次判断点(x, y)是否在多边形的内部;

射线法判断即可适用于任何(凸或凹)多边形;时间复杂度为O(n);

判断一个点是在多边形内部,边上还是在外部,时间复杂度为O(n);射线法可以正确用于凹多边形;

射线法是使用最广泛的算法,这是由于相比较其他算法而言,它不但可以正确使用在凹多边形上,而且不需要考虑精度误差问题。该算法思想是从点出发向右水平做

一条射线,计算该射线与多边形的边的相交点个数,当点不在多边形边上时,如果是奇数,那么点就一定在多边形内部,否则,在外部。

/*
射线法:判断一个点是在多边形内部,边上还是在外部,时间复杂度为O(n);
射线法可以正确用于凹多边形;
射线法是使用最广泛的算法,这是由于相比较其他算法而言,它不但可以正
确使用在凹多边形上,而且不需要考虑精度误差问题。该算法思想是从点出
发向右水平做一条射线,计算该射线与多边形的边的相交点个数,当点不在
多边形边上时,如果是奇数,那么点就一定在多边形内部,否则,在外部。
*/
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N = ;
const double eps = 1e-;
const int INF = 0x3f3f3f3f;
//////////////////////////////////////////////////////////////////
struct point
{
double x, y;
point(double x=, double y=) : x(x), y(y){}
friend point operator - (const point& p1, const point& p2)
{
return point(p1.x-p2.x, p1.y-p2.y);
}
friend double operator ^ (const point& p1, const point& p2)
{
return p1.x*p2.y - p1.y*p2.x;
}
};
//////////////////////////////////////////////////////////////////
struct Segment
{
point s, e;
};
//////////////////////////////////////////////////////////////////
///判断一个double类型的数是 0 <0 >0;
int Sign(double x)
{
if( fabs(x) < eps )return ;
if(x > )return ;
return -;
}
//////////////////////////////////////////////////////////////////
///判断o在ab的哪边;0:o在直线ab上; >0:在左边; <0:在右边;
double cross(point o, point a, point b)
{
return ((a-o)^(b-o));
}
//////////////////////////////////////////////////////////////////
///已知abc三点在一条直线上,判断点a是否在线段bc之间;<=0:在 >0:不在;
int Between(point a, point b, point c)
{
if(fabs(b.x-c.x) > fabs(b.y-c.y))
return Sign(min(b.x, c.x)-a.x)*Sign(max(b.x, c.x)-a.x);
else
return Sign(min(b.y, c.y)-a.y)*Sign(max(b.y, c.y)-a.y);
}
//////////////////////////////////////////////////////////////////
///判断点p0和线段S上,<=0:在,1:不在;
int PointOnSegment(point p0, Segment S)
{
if(Sign(cross(S.s, S.e, p0)) == )
return Between(p0, S.s, S.e);
return ;
}
//////////////////////////////////////////////////////////////////
///求线段a和线段b的交点个数;
int SegmentCross(Segment a, Segment b)
{
double x1 = cross(a.s, a.e, b.s);
double x2 = cross(a.s, a.e, b.e);
double x3 = cross(b.s, b.e, a.s);
double x4 = cross(b.s, b.e, a.e); if(Sign(x1*x2)< && Sign(x3*x4)<) return ;
if((Sign(x1)== && Between(b.s, a.s, a.e)<=) ||
(Sign(x2)== && Between(b.e, a.s, a.e)<=) ||
(Sign(x3)== && Between(a.s, b.s, b.e)<=) ||
(Sign(x4)== && Between(a.e, b.s, b.e)<=))
return ;
return ;
}
//////////////////////////////////////////////////////////////////
///判断点p0与含有n个节点的多边形的位置关系,p数组是顶点集合;
///返回0:边上或顶点上, 1:外面, -1:里面;
int PointInPolygon(point p0, point p[], int n)
{
Segment L, S;
point temp;
L.s = p0, L.e = point(INF, p0.y);///以p0为起点的射线L; int counts = ;
p[n] = p[]; for(int i=; i<=n; i++)
{
S.s = p[i-], S.e = p[i]; if(PointOnSegment(p0, S) <= ) return ;
if(S.s.y == S.e.y) continue;///和射线平行; if(S.s.y > S.e.y) temp = S.s;
else temp = S.e; if(PointOnSegment(temp, L) == -)
counts ++;
else if(SegmentCross(L, S) == )
counts ++;
}
if(counts%) return -;
return ;
}
//////////////////////////////////////////////////////////////////
int main()
{
point p[N];
int T, tCase = , n, q;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
for(int i=; i<n; i++)
scanf("%lf %lf", &p[i].x, &p[i].y);
scanf("%d", &q);
printf("Case %d:\n", tCase++);
for(int i=; i<=q; i++)
{
int x, y;
scanf("%d %d", &x, &y);
int ans = PointInPolygon(point(x, y), p, n);
if(ans == ) puts("No");
else puts("Yes");
}
}
return ;
}

最新文章

  1. 【转载】我眼中的Oracle性能优化
  2. 利用Spring中同名Bean相互覆盖的特性,定制平台的类内容。
  3. JVM中的Stack和Frame
  4. Cloning EBS from Linux 5 to Linux 6 Fails: &quot;Error While Loading Shared Libraries: libclntsh.so.10.1
  5. Android SQLite的ORM接口实现(一)---findAll和find的实现
  6. 删除src值为空的img标签
  7. php数据访问:pdo用法、事物回滚功能和放sql注入功能
  8. Java 面向对象编程——第一章 初识Java
  9. call &amp; apply
  10. 你不知道的JSON的高效率用法
  11. BLK-MD-BC04-B蓝牙模块开发说明
  12. oracle 修改索引现有表空间
  13. 关于centos6.5系统安装FTP服务和配置的方法
  14. 3 Sum Closest 解答
  15. Docker安装应用程序(Centos6.5_x64)
  16. Hibernate学习---用Session实现CURD
  17. Codeforces.226D.The table(构造)
  18. dd制作linux启动盘
  19. Linux 中的命令链接操作符
  20. logback基本入门

热门文章

  1. BZOJ4303 : 数列
  2. BZOJ3775 : 点和直线
  3. Android下载文件到SD卡
  4. 【Vijos】1218 数字游戏
  5. LCA的五种解法
  6. 看看 JDK 8 给我们带来什么(转)
  7. Java主要有那几种文件类型,各自作用
  8. java中的this与super的区别
  9. OpenCV学习笔记——滑动条开关
  10. 使用Grunt启动和运行