首页 > ACM题库 > HDU-杭电 > HDU 1756 Cupid’s Arrow-计算几何-[解题报告] C++
2013
12-23

HDU 1756 Cupid’s Arrow-计算几何-[解题报告] C++

Cupid’s Arrow

问题描述 :

传说世上有一支丘比特的箭,凡是被这支箭射到的人,就会深深的爱上射箭的人。
世上无数人都曾经梦想得到这支箭。Lele当然也不例外。不过他想,在得到这支箭前,他总得先学会射箭。
日子一天天地过,Lele的箭术也越来越强,渐渐得,他不再满足于去射那圆形的靶子,他开始设计各种各样多边形的靶子。
不过,这样又出现了新的问题,由于长时间地练习射箭,Lele的视力已经高度近视,他现在甚至无法判断他的箭射到了靶子没有。所以他现在只能求助于聪明的Acmers,你能帮帮他嘛?

输入:

本题目包含多组测试,请处理到文件结束。
在每组测试的第一行,包含一个正整数N(2<N<100),表示靶子的顶点数。
接着N行按顺时针方向给出这N个顶点的x和y坐标(0<x,y<1000)。
然后有一个正整数M,表示Lele射的箭的数目。
接下来M行分别给出Lele射的这些箭的X,Y坐标(0<X,Y<1000)。

输出:

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

样例输入:

4
10 10
20 10
20 5
10 5
2
15 8
25 8

样例输出:

Yes
No

/*
*  题意:判断点在多边形内
*  判点在任意多边形内,顶点按顺时针或逆时针给出
*/
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>

using namespace std;

const int N = 100;
const int offset = 1000;   //offset为多边形坐标上限
const double eps = 1e-8;

struct point {
    double x;
    double y;
}p[N], p1, p2;

bool isZero(double x) {//判断x是否接近0 
    return (x > 0 ? x : -x) < eps; 
}

double crossProd(point A, point B, point C) {
    return (B.x-A.x)*(C.y-A.y) - (B.y-A.y)*(C.x-A.x);
}

int inPolygon(int n) {
    int count, i = 0;
    p[n] = p[0];
    while (i < n) {
        p2.x = rand() + offset;  //随机取一个足够远的点p2 
        p2.y = rand() + offset;  //以p1为起点p2为终点做射线L 
        for (i=count=0; i<n; ++i) {//依次对多边形的每条边进行考察 
            if (isZero(crossProd(p1,p[i],p[i+1]))&&
            (p[i].x-p1.x)*(p[i+1].x-p1.x)<eps&&(p[i].y-p1.y)*(p[i+1].y-p1.y)<eps)
                return true;//点p1在边上,返回点p1在边上的信息 
            else if (isZero(crossProd(p1, p2, p[i]))) break;//点p[i]在射线p1p2上,停止本循环,另取p2 
            else if (crossProd(p[i], p[i+1], p1)*crossProd(p[i], p2, p[i+1])>eps &&//射线与边相交,统计交点数 
                     crossProd(p1, p2, p[i])*crossProd(p1, p[i+1], p2)>eps)  ++count;
        }
    }
    return count & 1;
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        for (int i=0; i<n; ++i) scanf ("%lf%lf", &p[i].x, &p[i].y);
        int m;
        scanf ("%d", &m);
        while (m--) {
            scanf ("%lf%lf", &p1.x, &p1.y);
            if (inPolygon(n)) printf ("Yes\n");
            else printf ("No\n");
        }
    }
    return 0;
}

 

解题报告转自:http://www.cnblogs.com/try86/archive/2012/04/22/2465416.html


  1. 您没有考虑 树的根节点是负数的情况, 若树的根节点是个很大的负数,那么就要考虑过不过另外一边子树了

  2. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。