Cupid's Arrow[HDU1756]

Cupid's Arrow

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

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

10 10

20 10

20 5

10 5

15 8

25 8

Sample Output

Yes

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
//#include <algorithm>
namespace Geometry {
#define eps (1e-8)
    class point {
    public:
        double x, y;
        point() {}
        point(const point &p): x(p.x), y(p.y) {}
        point(double a, double b): x(a), y(b) {}
        point operator + (const point & p)const {
            point ret;
            ret.x = x + p.x, ret.y = y + p.y;
            return ret;
        }
        point operator - (const point & p)const {
            point ret;
            ret.x = x - p.x, ret.y = y - p.y;
            return ret;
        }
        //dot product
        double operator * (const point & p)const {
            return x * p.x + y * p.y;
        }
        //cross product
        double operator ^ (const point & p)const {
            return x * p.y - p.x * y;
        }
        bool operator < (const point & p)const {
            if (fabs(x - p.x) < eps) {
                return y < p.y;
            }
            return x < p.x;
        }
        double mold() {
            return sqrt(x * x + y * y);
        }
    };
    double cp(point a, point b, point o) {
        return (a - o) ^ (b - o);
    }
    double dp(point a, point b, point o) {
        return (a - o) * (b - o);
    }
    class line {
    public:
        point A, B;
        line() {}
        line(point a, point b): A(a), B(b) {}
        bool IsLineCrossed(const line &l)const {
            point v1, v2;
            double c1, c2;
            v1 = B - A, v2 = l.A - A;
            c1 = v1 ^ v2;
            v2 = l.B - A;
            c2 = v1 ^ v2;
            if (c1 * c2 >= 0) {
                return false;
            }
            v1 = l.B - l.A, v2 = A - l.A;
            c1 = v1 ^ v2;
            v2 = B - l.A;
            c2 = v1 ^ v2;
            if (c1 * c2 >= 0) {
                return false;
            }
            return true;
        }
    };
    /*
    **  get the convex closure of dot set,store in array s.
    **  return the amount of the dot in the convex closure
    */
    int Graham(point * p, point * s, int n) {
        std::sort(p, p + n);
        int top, m;
        s[0] = p[0];
        s[1] = p[1];
        top = 1;
        for (int i = 2; i < n; i++) {
            while (top > 0 && cp(p[i], s[top], s[top - 1]) >= 0) {
                top--;
            }
            s[++top] = p[i];
        }
        m = top;
        s[++top] = p[n - 2];
        for (int i = n - 3; i >= 0; i--) {
            while (top > m && cp(p[i], s[top], s[top - 1]) >= 0) {
                top--;
            }
            s[++top] = p[i];
        }
        return top;
    }
    int dcmp(double x) {
        if (x < -eps) {
            return -1;
        } else {
            return (x > eps);
        }
    }
    //if the point p0 on the segment consists of point p1 and p2
    int PointOnSegment(point p0, point p1, point p2) {
        return dcmp(cp(p1, p2, p0)) == 0 && dcmp(dp(p1, p2, p0)) <= 0;
    }
    /*
    **  if the point pt in polygon consists of the dots in array p
    **  0:outside
    **  1:inside
    **  2:on the border
    */
    int PointInPolygon(point pt, point * p, int n) {
        int i, k, d1, d2, wn = 0;
        p[n] = p[0];
        for (i = 0; i < n; i++) {
            if (PointOnSegment(pt, p[i], p[i + 1])) {
                return 2;
            }
            k = dcmp(cp(p[i + 1], pt, p[i]));
            d1 = dcmp(p[i + 0].y - pt.y);
            d2 = dcmp(p[i + 1].y - pt.y);
            if (k > 0 && d1 <= 0 && d2 > 0) {
                wn++;
            }
            if (k < 0 && d2 <= 0 && d1 > 0) {
                wn--;
            }
        }
        return wn != 0 ? 1 : 0;
    }
}
//using namespace Geometry;
using namespace Geometry;
point p[105];
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    int n, m;
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; i++) {
            scanf("%lf%lf", &p[i].x, &p[i].y);
        }
        scanf("%d", &m);
        point pt;
        for (int i = 0; i < m; i++) {
            scanf("%lf%lf", &pt.x, &pt.y);
            if (PointInPolygon(pt, p, n) == 1) {
                printf("Yes
");
            } else {
                printf("No
");
            }
        }
    }
    return 0;
}

View Code