Cupid's Arrow
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 849 Accepted Submission(s): 306
Problem Description
传说世上有一支丘比特的箭，凡是被这支箭射到的人，就会深深的爱上射箭的人。
世上无数人都曾经梦想得到这支箭。Lele当然也不例外。不过他想，在得到这支箭前，他总得先学会射箭。
日子一天天地过，Lele的箭术也越来越强，渐渐得，他不再满足于去射那圆形的靶子，他开始设计各种各样多边形的靶子。
不过，这样又出现了新的问题，由于长时间地练习射箭，Lele的视力已经高度近视，他现在甚至无法判断他的箭射到了靶子没有。所以他现在只能求助于聪明的Acmers，你能帮帮他嘛？
世上无数人都曾经梦想得到这支箭。Lele当然也不例外。不过他想，在得到这支箭前，他总得先学会射箭。
日子一天天地过，Lele的箭术也越来越强，渐渐得，他不再满足于去射那圆形的靶子，他开始设计各种各样多边形的靶子。
不过，这样又出现了新的问题，由于长时间地练习射箭，Lele的视力已经高度近视，他现在甚至无法判断他的箭射到了靶子没有。所以他现在只能求助于聪明的Acmers，你能帮帮他嘛？
Input
本题目包含多组测试，请处理到文件结束。
在每组测试的第一行，包含一个正整数N(2<N<100),表示靶子的顶点数。
接着N行按顺时针方向给出这N个顶点的x和y坐标(0<x,y<1000)。
然后有一个正整数M，表示Lele射的箭的数目。
接下来M行分别给出Lele射的这些箭的X,Y坐标(0<X,Y<1000)。
在每组测试的第一行，包含一个正整数N(2<N<100),表示靶子的顶点数。
接着N行按顺时针方向给出这N个顶点的x和y坐标(0<x,y<1000)。
然后有一个正整数M，表示Lele射的箭的数目。
接下来M行分别给出Lele射的这些箭的X,Y坐标(0<X,Y<1000)。
Output
对于每枝箭，如果Lele射中了靶子，就在一行里面输出"Yes",否则输出"No"。
Sample Input
4
10 10
20 10
20 5
10 5
2
15 8
25 8
Sample Output
Yes
No
Author
linle
Source
Recommend
计算几何：判断点在多边形内。
开始看这类题算法感觉不难，就是需要考虑的很多，结果自己写模板的时候才发现真心麻烦。WA了好多次，发现是自己想漏了。最后一次提交的时候心情还是很忐忑，不过总算AC了。
下面是这类题算法的思路，我就是照着下面链接的思路写的模板，具体我就不写在这里了，链接里介绍的很详细：
我的模板（未优化）：
//判断点q是否在多边形内
//任意凸或者凹多边形
//顶点集合p[]按逆时针或者顺时针顺序存储(1..pointnum)
struct Point{
double x,y;
};
struct Line{
Point p1,p2;
};
double xmulti(Point p1,Point p2,Point p0) //求p1p0和p2p0的叉积,如果大于0,则p1在p2的顺时针方向
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
double Max(double a,double b)
{
return a>b?a:b;
}
double Min(double a,double b)
{
return a<b?a:b;
}
bool ponls(Point q,Line l) //判断点q是否在线段l上
{
if(q.x > Max(l.p1.x,l.p2.x) || q.x < Min(l.p1.x,l.p2.x)
|| q.y > Max(l.p1.y,l.p2.y) || q.y < Min(l.p1.y,l.p2.y) )
return false;
if(xmulti(l.p1,l.p2,q)==) //点q不在l的延长线或者反向延长线上，如果叉积再为0，则确定点q在线段l上
return true;
else
return false;
}
bool pinplg(int pointnum,Point p[],Point q)
{
Line s;
int c = ;
for(int i=;i<=pointnum;i++){ //多边形的每条边s
if(i==pointnum)
s.p1 = p[pointnum],s.p2 = p[];
else
s.p1 = p[i],s.p2 = p[i+];
if(ponls(q,s)) //点q在边s上
return true;
if(s.p1.y != s.p2.y){ //s不是水平的
Point t;
t.x = q.x - ,t.y = q.y;
if( (s.p1.y == q.y && s.p1.x <=q.x) || (s.p2.y == q.y && s.p2.x <= q.x) ){ //s的一个端点在L上
int tt;
if(s.p1.y == q.y)
tt = ;
else if(s.p2.y == q.y)
tt = ;
int maxx;
if(s.p1.y > s.p2.y)
maxx = ;
else
maxx = ;
if(tt == maxx) //如果这个端点的纵坐标较大的那个端点
c++;
}
else if(xmulti(s.p1,t,q)*xmulti(s.p2,t,q) <= ){ //L和边s相交
Point lowp,higp;
if(s.p1.y > s.p2.y)
lowp.x = s.p2.x,lowp.y = s.p2.y,higp.x = s.p1.x,higp.y = s.p1.y;
else
lowp.x = s.p1.x,lowp.y = s.p1.y,higp.x = s.p2.x,higp.y = s.p2.y;
if(xmulti(q,higp,lowp)>=)
c++;
}
}
}
if(c%==)
return false;
else
return true;
}
吉林大学的模板，很精练：
/*===============================================
| 判断点q是否在多边形内
其中多边形是任意的凸或凹多边形，
Polygon中存放多边形的逆时针顶点序列
================================================*/
int pinplg(int vcount,Lpoint Polygon[],Lpoint q)
{
int c=,i,n;
Llineseg l1,l2;
l1.a=q; l1.b=q; l1.b.x=infinity; n=vcount;
for (i=;i<vcount;i++) {
l2.a=Polygon[i];
l2.b=Polygon[(i+)%n];
if ((lsinterls_A(l1,l2))||
(
(ponls(l1,Polygon[(i+)%n]))&&
(
(!ponls(l1,Polygon[(i+)%n]))&&
(xmulti(Polygon[i],Polygon[(i+)%n],l1.a) *
xmulti(Polygon[(i+)%n],Polygon[(i+)%n],l1.a)>)
||
(ponls(l1,Polygon[(i+)%n]))&&
(xmulti(Polygon[i],Polygon[(i+)%n],l1.a) *
xmulti(Polygon[(i+)%n],Polygon[(i+)%n],l1.a)>)
) ) ) c++;
}
return(c%!=);
}
题目代码：
#include <iostream>
using namespace std;
//判断点q是否在多边形内
//任意凸或者凹多边形
//顶点集合p[]按逆时针或者顺时针顺序存储(1..pointnum)
struct Point{
double x,y;
};
struct Line{
Point p1,p2;
};
double xmulti(Point p1,Point p2,Point p0) //求p1p0和p2p0的叉积,如果大于0,则p1在p2的顺时针方向
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
double Max(double a,double b)
{
return a>b?a:b;
}
double Min(double a,double b)
{
return a<b?a:b;
}
bool ponls(Point q,Line l) //判断点q是否在线段l上
{
if(q.x > Max(l.p1.x,l.p2.x) || q.x < Min(l.p1.x,l.p2.x)
|| q.y > Max(l.p1.y,l.p2.y) || q.y < Min(l.p1.y,l.p2.y) )
return false;
if(xmulti(l.p1,l.p2,q)==) //点q不在l的延长线或者反向延长线上，如果叉积再为0，则确定点q在线段l上
return true;
else
return false;
}
bool pinplg(int pointnum,Point p[],Point q)
{
Line s;
int c = ;
for(int i=;i<=pointnum;i++){ //多边形的每条边s
if(i==pointnum)
s.p1 = p[pointnum],s.p2 = p[];
else
s.p1 = p[i],s.p2 = p[i+];
if(ponls(q,s)) //点q在边s上
return true;
if(s.p1.y != s.p2.y){ //s不是水平的
Point t;
t.x = q.x - ,t.y = q.y;
if( (s.p1.y == q.y && s.p1.x <=q.x) || (s.p2.y == q.y && s.p2.x <= q.x) ){ //s的一个端点在L上
int tt;
if(s.p1.y == q.y)
tt = ;
else if(s.p2.y == q.y)
tt = ;
int maxx;
if(s.p1.y > s.p2.y)
maxx = ;
else
maxx = ;
if(tt == maxx) //如果这个端点的纵坐标较大的那个端点
c++;
}
else if(xmulti(s.p1,t,q)*xmulti(s.p2,t,q) <= ){ //L和边s相交
Point lowp,higp;
if(s.p1.y > s.p2.y)
lowp.x = s.p2.x,lowp.y = s.p2.y,higp.x = s.p1.x,higp.y = s.p1.y;
else
lowp.x = s.p1.x,lowp.y = s.p1.y,higp.x = s.p2.x,higp.y = s.p2.y;
if(xmulti(q,higp,lowp)>=)
c++;
}
}
}
if(c%==)
return false;
else
return true;
}
int main()
{
int N,M;
Point p[];
while(cin>>N){
for(int i=;i<=N;i++)
cin>>p[i].x>>p[i].y;
cin>>M;
while(M--){
Point q;
cin>>q.x>>q.y;
if(pinplg(N,p,q))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
}
return ;
}
Freecode : www.cnblogs.com/yym2013