题意：在二维坐标系中，给定一个定点p，再依次给出一个任意多边形的所有顶点，问点p是否在所在多边形内部。在的话输出yes，否则输出no。
思路：
这一题有好几种算法，这里考虑用射线判断法：
以点P为端点，向左方作射线L，由于多边形是有界的，所以射线L的左端一定在多边形外，考虑沿着L从无穷远处开始自左向右移动，遇到和多边形的第一个交点的时候，进入到了多边形的内部，遇到第二个交点的时候，离开了多边形，……所以很容易看出当L和多边形的交点数目C是奇数的时候，P在多边形内，是偶数的话P在多边形外。
但是有些特殊情况要加以考虑。如果L和多边形的顶点相交，有些情况下交点只能计算一个，有些情况下交点不应被计算（你自己画个图就明白了）；如果L和多边形的一条边重合，这条边应该被忽略不计。为了统一起见，我们在计算射线L和多边形的交点的时候，1。对于多边形的水平边不作考虑；2。对于多边形的顶点和L相交的情况，如果该顶点是其所属的边上纵坐标较大的顶点，则计数，否则忽略；3。对于P在多边形边上的情形，直接可判断P属于多边行。
其中要用到几种判断方法：
1.点在线上：
设点为Q，线段为P1P2 ，判断点Q在该线段上的依据是：( Q - P1 ) × ( P2 - P1 ) = 0 且 Q 在以 P1，P2为对角顶点的矩形内。前者保证Q点在直线P1P2上，后者是保证Q点不在线段P1P2的延长线或反向延长线上
2.线段相交（分两步）：
(1)快速排斥试验
设以线段 P1P2 为对角线的矩形为R， 设以线段 Q1Q2 为对角线的矩形为T，如果R和T不相交，显然两线段不会相交。
• (2)跨立试验
如果两线段相交，则两线段必然相互跨立对方。若P1P2跨立Q1Q2 ，则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧，即( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0。上式可改写成( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) > 0。当 ( P1 - Q1 ) × ( Q2 - Q1 ) = 0 时，说明 ( P1 - Q1 ) 和 ( Q2 - Q1 )共线，但是因为已经通过快速排斥试验，所以 P1 一定在线段 Q1Q2上；同理，( Q2 - Q1 ) ×(P2 - Q1 ) = 0 说明 P2 一定在线段 Q1Q2上。所以判断P1P2跨立Q1Q2的依据是：( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) >= 0。同理判断Q1Q2跨立P1P2的依据是：( Q1 - P1 ) × ( P2 - P1 ) * ( P2 - P1 ) × ( Q2 - P1 ) >= 0。
代码：
#include"iostream"
#include"string"
#include"cstdio"
#include"algorithm"
#include"cmath"
#define E 1e-8
#define MAX 1e5
#define M 102
using namespace std;
struct Point /*定义点*/
{
double x,y;
};
struct Segment /*定义线段*/
{
Point a,b;
};
double min(double x,double y)
{
return x>y?y:x;
}
double max(double x,double y)
{
return x>y?x:y;
}
double xmult(Point p1,Point p2,Point p0) /*计算两向量的叉积*/ //计算叉积
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
bool is_online(Point p,Segment s) /*判断p是否在线段s上*/
{
if(fabs(xmult(s.a,p,s.b))<=E&&min(s.a.x,s.b.x)<=p.x&&
p.x<=max(s.a.x,s.b.x)&&min(s.a.y,s.b.y)<=p.y&&p.y<=max(s.a.y,s.b.y))
return true;
return false;
}
bool is_segment_crossing(Segment u,Segment v) /*判断两线段是否相交*/
{
return((max(u.a.x,u.b.x)>=min(v.a.x,v.b.x))&&
(max(v.a.x,v.b.x)>=min(u.a.x,u.b.x))&&
(max(u.a.y,u.b.y)>=min(v.a.y,v.b.y))&&
(max(v.a.y,v.b.y)>=min(u.a.y,u.b.y))&&
(xmult(v.a,u.b,u.a)*xmult(u.b,v.b,u.a)>=0)&&
(xmult(u.a,v.b,v.a)*xmult(v.b,u.b,v.a)>=0));
}
bool is_in_area(Point p,Point s[],int len)/*判断点p是否在以边点顺序排列的点集s所围成的多边形内*/
{
Segment seg;
Segment pp;
int num=0;
Point MM;/*定义无穷点*/
MM.y=p.y;
MM.x=MAX;
pp.a=p;
pp.b=MM;/*构造一条平行于x轴的以p为端点的右射线pp*/
for(int i=0;i<len;i++)
{
seg.a=s[i];
seg.b=s[(i+1)%len];
if(is_online(p,seg))/*点p在边上*/
return true;
if(fabs(seg.a.y-seg.b.y)<E)/*水平*/
continue;
if(is_online(seg.a,pp))/*边的一端点在射线上*/
{
if(seg.a.y>seg.b.y)
num++;
}
else if(is_online(seg.b,pp))
{
if(seg.b.y>seg.a.y)
num++;
}
else if(is_segment_crossing(pp,seg))
num++;
}
//cout<<num<<"::"<<endl;
if(num%2==1)
return true;
return false;
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
Point p;
Point s[M];
int num;
scanf("%d",&num);
scanf("%lf%lf",&p.x,&p.y);
for(int i=0;i<num;i++)
{
scanf("%lf%lf",&s[i].x,&s[i].y);
}
if(is_in_area(p,s,num))
printf("yes\n");
else
printf("no\n");
}
}
