HDU1756 Cupid's Arrow (判断点在多边形内) 省赛训练3 计算几何

Cupid’s Arrow

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

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

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

 

Sample Output

Yes No

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
#define maxn 111

struct point {
    double x, y;
    point (double _x = 0, double _y = 0) : x(_x), y(_y) {}
    point operator - (point a) const {
        return point (x-a.x, y-a.y);
    }
    bool operator < (const point &a) const {
        return x < a.x || (x == a.x && y < a.y);
    }
}p[maxn];

const double eps = 1e-10;
int dcmp (double x) {
    if (fabs (x) < eps)
        return 0;
    else return x < 0 ? -1 : 1;
}
double cross (point a, point b) {
    return a.x*b.y-a.y*b.x;
}
double dot (point a, point b) {
    return a.x*b.x + a.y*b.y;
}
bool PointOnLine (point a1, point a2, point p) {//判断点p是不是在线段a1a2上
    if (dcmp (cross (a1-p, a2-p)) == 0 && dcmp (dot (a1-p, a2-p)) <= 0)
        return 1;
    return 0;
}

int n, m;

bool PointInPolygon (point a, point *b) {
    int w = 0;
    for (int i = 0; i < n; i++) {
        if (PointOnLine (b[i], b[(i+1)%n], a))
            return 0;
        int k = dcmp (cross (b[(i+1)%n]-b[i], a-b[i]));
        int d1 = dcmp (b[i].y - a.y);
        int d2 = dcmp (b[(i+1)%n].y - a.y);
        if (k > 0 && d1 <= 0 && d2 > 0)
            w++;
        if (k < 0 && d2 <= 0 && d1 > 0)
            w--;
    }
    if (w != 0)
        return 1;
    return 0;
}

int main () {
    //freopen ("in", "r", stdin);
    ios::sync_with_stdio(0);
    while (cin >> n) {
        for (int i = 0; i < n; i++) {
            cin >> p[i].x >> p[i].y;
        }
        cin >> m;
        while (m--) {
            point tmp;
            cin >> tmp.x >> tmp.y;
            if (PointInPolygon (tmp, p)) {
                cout << "Yes" << endl;
            }
            else cout << "No" << endl;
        }
    }
    return 0;
}