HDU-1756 Cupid's Arrow 判断点是不是在多边形内部
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1756
判断点是否在多边形内部
从点p做一条射线，看射线和多边形的交点有几个,奇数个为相交，偶数个不相交。。。
具体做法如下:
以点P为端点，向左方作射线L，由于多边形是有界的，所以射线L的左端一定在多边形外，考虑沿着L从无穷远处开始自左向右移动，遇到和多边形的第一个交点的时候，进入到了多边形的内部，遇到第二个交点的时候，离开了多边形，……所以很容易看出当L和多边形的交点数目C是奇数的时候，P在多边形内，是偶数的话P在多边形外。
但是有些特殊情况要加以考虑。如图下图(a)(b)(c)(d)所示。在图(a)中，L和多边形的顶点相交，这时候交点只能计算一个；在图(b)中，L和多边形顶点的交点不应被计算；在图(c)和(d) 中，L和多边形的一条边重合，这条边应该被忽略不计。如果L和多边形的一条边重合，这条边应该被忽略不计。
为了统一起见，我们在计算射线L和多边形的交点的时候，1。对于多边形的水平边不作考虑；2。对于多边形的顶点和L相交的情况，如果该顶点是其所属的边上纵坐标较大的顶点，则计数，否则忽略；3。对于P在多边形边上的情形，直接可判断P属于多边行。由此得出算法的伪代码如下：
count ← 0;
以P为端点，作从右向左的射线L;
for 多边形的每条边s
do if P在边s上
then return true;
if s不是水平的
then if s的一个端点在L上
if 该端点是s两端点中纵坐标较大的端点
then count ← count+1
else if s和L相交
then count ← count+1;
if count mod 2 = 1
then return true;
else return false;
其中做射线L的方法是：设P'的纵坐标和P相同，横坐标为正无穷大（很大的一个正数），则P和P'就确定了射线L。
判断点是否在多边形中的这个算法的时间复杂度为O(n)。
另外还有一种算法是用带符号的三角形面积之和与多边形面积进行比较，这种算法由于使用浮点数运算所以会带来一定误差，不推荐大家使用。
My code:
//STATUS:C++_AC_15MS_244KB
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<vector>
#include<queue>
#include<math.h>
#include<map>
#include<set>
using namespace std;
#define LL __int64
#define pii pair<int,int>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int MAX=110,INF=200000000;
const double esp=1e-6;
int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
struct Line{
int x1,y1,x2,y2;
};
struct Node{
int x,y;
}nod[MAX];
int chaji(Node &a,Node &b){
return a.x*b.y-b.x*a.y;
}
int quick(Node &l1,Node &l2,Node &r1,Node &r2);
int las(Node &l1,Node &l2,Node &r1,Node &r2);
int ponls(Node &a,Node &b,Node &p);
int pinply(int num_node,Node nod[],Node &p);
int n,m;
int main()
{
// freopen("in.txt","r",stdin);
int i;
Node p;
while(~scanf("%d",&n))
{
for(i=0;i<n;i++)
scanf("%d%d",&nod[i].x,&nod[i].y);
scanf("%d",&m);
while(m--){
scanf("%d%d",&p.x,&p.y);
if(pinply(n,nod,p))
printf("Yes\n");
else printf("No\n");
}
}
return 0;
}
int pinply(int num_node,Node nod[],Node &p)
{
int i,j,cou=0;
Node ray;
ray.x=-1,ray.y=p.y;
for(i=0;i<num_node;i++){
j=(i+1)%num_node;
if(ponls(nod[i],nod[j],p))return 0;
if(nod[i].y!=nod[j].y){
if(ponls(p,ray,nod[i]) && nod[i].y==max(nod[i].y,nod[j].y))
cou++;
else if(ponls(p,ray,nod[j]) && nod[j].y==max(nod[i].y,nod[j].y))
cou++;
else if(quick(nod[i],nod[j],p,ray) && las(nod[i],nod[j],p,ray)
&& las(p,ray,nod[i],nod[j]))
cou++;
}
}
return cou&1;
}
int ponls(Node &a,Node &b,Node &p)
{
if( (p.x==a.x && p.y==a.y) || (p.x==b.x && p.y==b.y) )return 2;
Node r1,r2;
r1.x=a.x-b.x,r1.y=a.y-b.y;
r2.x=p.x-b.x,r2.y=p.y-b.y;
if(!chaji(r1,r2) && p.x>=min(a.x,b.x) && p.x<=max(a.x,b.x)
&& p.y>=min(a.y,b.y) && p.y<=max(a.y,b.y))
return 1;
return 0;
}
int quick(Node &l1,Node &l2,Node &r1,Node &r2)
{
if(min(l1.x,l2.x)>max(r1.x,r2.x)
|| min(l1.y,l2.y)>max(r1.y,r2.y)
|| max(l1.x,l2.x)<min(r1.x,r2.x)
|| max(l1.y,l2.y)<min(r1.y,r2.y))
return 0;
return 1;
}
int las(Node &l1,Node &l2,Node &r1,Node &r2)
{
Node a,b,c;
a.x=l1.x-r1.x;
a.y=l1.y-r1.y;
b.x=r2.x-r1.x;
b.y=r2.y-r1.y;
c.x=l2.x-r1.x;
c.y=l2.y-r1.y;
if( ((a.x*b.y)-(b.x*a.y))*((c.x*b.y)-(b.x*c.y))<0)return 1;
else return 0;
}