学步园

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=81

题目的很简单：给你一个多边形，再给你一系列的点，问你这些是否在多边形内。输出这些点与多边形的关系。。

学到了一种射线法判断点是否在多变型内。通过点在水平或者竖直引一条射线，看与多边形的交点个数。奇数就是在多边形内，偶数就是在多边形外。最开始，我是很怀疑这种方法的。主要还是射线穿过端点的情况。

对于上面的情况：

我们对于穿过端点的射线，交点算几次呢？？我们这里只算一次。为了统一，我们要求这样来进行统计交点。

1.平行和重合于射线的多边形边不算。

2.对于相交于端点的交点，如果该点是该边的较高点（y值较大），算一次。。

基本上这样就可以了。。

Code：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

const int N = 105;
const double eps = 1e-8;
const double pi = acos(-1);
const double INF = 0x3f3f3f3f;
//点
struct POINT
{
    double x, y;
    POINT(){ }
    POINT(double a, double b){
        x = a;
        y = b;
    }
}p[N];
//线段
struct Seg
{
    POINT a, b;
    Seg() { }
    Seg(POINT x, POINT y){
        a = x;
        b = y;
    }
};
//直线
struct Line
{
    POINT a, b;
    Line() {}
    Line(POINT x, POINT y){
        a = x;
        b = y;
    }
};
//叉乘
double cross(POINT o, POINT a, POINT b)
{
    return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);
}
//求两点间的距离
double dis(POINT a, POINT b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
int n, m, k;

//两条直线的位置关系，平行，重合和相交
int Line_cross(Seg l1, Seg l2)
{
    //两条直线平行
    if(fabs(cross(l1.a, l2.a, l2.b) - cross(l1.b, l2.a, l2.b)) < eps && fabs(cross(l1.a, l2.a, l2.b)) > eps) return 0;
    //重合..
    if(fabs(cross(l1.a, l2.a, l2.b)) < eps && fabs(cross(l1.b, l2.a, l2.b)) < eps) return 2;
    //有交点///
    return 1;
}

//判断点在线段上
bool On_Seg(POINT a, Seg s)
{
    if(fabs(cross(a, s.a, s.b)) > eps) return false;
    double maxx = max(s.a.x, s.b.x), minx = min(s.a.x, s.b.x);
    double maxy = max(s.a.y, s.b.y), miny = min(s.a.y, s.b.y);
    if(a.x >= minx && a.x <= maxx && a.y >= miny && a.y <= maxy) return true;
    return false;
}
//判断线段相交
bool Seg_cross(Seg s1, Seg s2)
{
    double cs1 = cross(s1.a, s2.a, s2.b);
    double cs2 = cross(s1.b, s2.a, s2.b);
    double cs3 = cross(s2.a, s1.a, s1.b);
    double cs4 = cross(s2.b, s1.a, s1.b);
    // 互相跨立
    if(cs1 * cs2 < 0 && cs3 * cs4 < 0) return true;
    if(On_Seg(s1.a, s2)) return true;
    if(On_Seg(s1.b, s2)) return true;
    if(On_Seg(s2.a, s1)) return true;
    if(On_Seg(s2.b, s1)) return true;
    return false;
}

bool PointInPolygon(POINT q)
{
    int cnt = 0;
    Seg s(q, POINT(INF, q.y));
    p[n] = p[0];
    for(int i = 0; i < n; i ++){
        if(On_Seg(q, Seg(p[i], p[i + 1]))) {
            return true;
        }
        //平行重合者不算...
        if(Line_cross(s, Seg(p[i], p[i + 1])) == 0 || Line_cross(s, Seg(p[i], p[i + 1])) == 2) continue;
        if(!Seg_cross(s, Seg(p[i], p[i + 1]))) continue;
        int on = -1;
        if(On_Seg(p[i], s)) on = i;
        if(On_Seg(p[i + 1], s)) on = i + 1;
        if(on != -1){
            if(fabs(p[on].y - max(p[i].y, p[i + 1].y)) < eps)
            cnt ++;
        }
        else cnt ++;
    }
    return cnt % 2;
}
int main()
{
//    freopen("11.txt", "r", stdin);
    k = 1;
    while(scanf("%d", &n) && n){
        scanf("%d", &m);
        for(int i = 0; i < n; i ++){
            scanf("%lf %lf", &p[i].x, &p[i].y);
        }
        if(k != 1) puts("");
        printf("Problem %d:\n", k ++);
        for(int i = 0; i < m; i ++){
            POINT test;
            scanf("%lf %lf", &test.x, &test.y);
            if(PointInPolygon(test)) puts("Within");
            else puts("Outside");
        }
    }
    return 0;
}

----->

又学习了。。