HDU 1756 Cupid's Arrow（判断点是否在多边形内部)

本文主要是介绍HDU 1756 Cupid's Arrow（判断点是否在多边形内部)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Cupid's Arrow

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 702 Accepted Submission(s): 252

Problem Description

传说世上有一支丘比特的箭，凡是被这支箭射到的人，就会深深的爱上射箭的人。
世上无数人都曾经梦想得到这支箭。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)。

Output

对于每枝箭，如果Lele射中了靶子，就在一行里面输出"Yes",否则输出"No"。

Sample Input

Sample Output

  Yes
No

Author

linle

Source

2007省赛集训队练习赛（6）_linle专场

这种题目有点巧看你随机数选的好不好，就是当前的点和一个无穷远的一个点组成一条线段，然后判断这条线段与边是否有交点

首先与顶点相交不算（这个就看你选的随机数了，选的好就是没有，选的不好就是有，不过也可以多试几次）

而且、如果交点个数是奇数那么在内部，否则在外部

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;
#define eps 1e-8
struct point
{double x;double y;
}po[10000],temp;
double multi(point p0, point p1, point p2)//j计算差乘
{   return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}
bool across(point s1,point e1,point s2,point e2)//判断线段是否相交（非规范相交）
{returnmulti(s1,e1,s2)*multi(s1,e1,e2) < -eps&&multi(s2,e2,s1)*multi(s2,e2,e1) < -eps;
}
int main()
{int n,t;int i,j,k;int count;point temp1;while(scanf("%d",&n)!=EOF){for(i=0;i<n;i++)scanf("%lf%lf",&po[i].x,&po[i].y);scanf("%d",&t);while(t--){count=0;scanf("%lf%lf",&temp.x,&temp.y);temp1=temp;temp1.x+=100008;temp1.y+=98430;po[i]=po[0];for(i=0;i<n;i++)if(across(temp,temp1,po[i],po[i+1]))count++;if(count==0 || count%2==0)printf("No\n");elseprintf("Yes\n");}}return 0;
}

这篇关于HDU 1756 Cupid's Arrow（判断点是否在多边形内部)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！