cupid's arrow(计算几何) .cpp

杭电acm解题报告2001---2099.

#include <cmath>
#include <cstdio>
#include <memory.h>
#include <algorithm>
using namespace std;
typedef double TYPE;
#define Abs(x) (((x)>0)?(x):(-(x)))
#define Sgn(x) (((x)<0)?(-1):(1))
#define Max(a,b) (((a)>(b))?(a):(b))
#define Min(a,b) (((a)<(b))?(a):(b))
#define Epsilon 1e-8
#define Infinity 1e+10
#define Pi 3.14159265358979323846
TYPE Deg2Rad(TYPE deg){return (deg * Pi / 180.0);}
TYPE Rad2Deg(TYPE rad){return (rad * 180.0 / Pi);}
TYPE Sin(TYPE deg){return sin(Deg2Rad(deg));}
TYPE Cos(TYPE deg){return cos(Deg2Rad(deg));}
TYPE ArcSin(TYPE val){return Rad2Deg(asin(val));}
TYPE ArcCos(TYPE val){return Rad2Deg(acos(val));}
TYPE Sqrt(TYPE val){return sqrt(val);}

//点
struct POINT
{
  TYPE x;
  TYPE y;
  POINT() : x(0), y(0) {};
  POINT(TYPE _x_, TYPE _y_) : x(_x_), y(_y_) {};
};
// 两个点的距离
TYPE Distance(const POINT & a, const POINT & b)
{
  return Sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
//线段
struct SEG
{
  POINT a; //起点
  POINT b; //终点
  SEG() {};
  SEG(POINT _a_, POINT _b_):a(_a_),b(_b_) {};
};

void Coefficient(const POINT & p,const TYPE a,TYPE & A,TYPE & B,TYPE & C)
{
  A = Cos(a);
  B = Sin(a);
  C = - (p.y * B + p.x * A);
}

// 两线段叉乘
TYPE Cross2(const SEG & p, const SEG & q)
{
  return (p.b.x - p.a.x) * (q.b.y - q.a.y) - (q.b.x - q.a.x) * (p.b.y - p.a.y);
}
//有公共端点O叉乘,并判拐,若正p0->p1->p2拐向左
TYPE Cross(const POINT & a, const POINT & b, const POINT & o)
{
  return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);
}
//判等(值，点，直线)
bool IsEqual(TYPE a, TYPE b)
{
  return (Abs(a - b) < Epsilon);
}
bool IsEqual(const POINT & a, const POINT & b)
{
  return (IsEqual(a.x, b.x) && IsEqual(a.y, b.y));
}

// 判断点是否在线段上
bool IsOnSeg(const SEG & seg, const POINT & p)
{
  return (IsEqual(p, seg.a) || IsEqual(p, seg.b)) ||
    (((p.x - seg.a.x) * (p.x - seg.b.x) < 0 ||
    (p.y - seg.a.y) * (p.y - seg.b.y) < 0) &&
    (IsEqual(Cross(seg.b, p, seg.a), 0)));
}
//判断两条线断是否相交，端点重合算相交
bool IsIntersect(const SEG & u, const SEG & v)
{
  return (Cross(v.a, u.b, u.a) * Cross(u.b, v.b, u.a) >= 0) &&
    (Cross(u.a, v.b, v.a) * Cross(v.b, u.b, v.a) >= 0) &&
    (Max(u.a.x, u.b.x) >= Min(v.a.x, v.b.x)) &&
    (Max(v.a.x, v.b.x) >= Min(u.a.x, u.b.x)) &&
    (Max(u.a.y, u.b.y) >= Min(v.a.y, v.b.y)) &&
    (Max(v.a.y, v.b.y) >= Min(u.a.y, u.b.y));
}

// 多边形 ,逆时针或顺时针给出x,y
struct POLY
{
  int n;     //n个点
  TYPE * x;   //x,y为点的指针，首尾必须重合
  TYPE * y;
  POLY() : n(0), x(NULL), y(NULL) {};
  POLY(int _n_, const TYPE * _x_, const TYPE * _y_)
  {
    n = _n_;
    x = new TYPE[n + 1];
    memcpy(x, _x_, n*sizeof(TYPE));
    x[n] = _x_[0];
    y = new TYPE[n + 1];
    memcpy(y, _y_, n*sizeof(TYPE));
    y[n] = _y_[0];
  }
};

//多边形的边
SEG Edge(const POLY & poly, int idx)
{
  idx %= poly.n;
  return SEG(POINT(poly.x[idx], poly.y[idx]),
    POINT(poly.x[idx + 1], poly.y[idx + 1]));
}

//判断点是否在多边形内部
bool IsInPoly(const POLY & poly, const POINT & p)
{
  SEG L(p, POINT(Infinity, p.y));

  int count = 0;
  for (int i = 0; i < poly.n; i++)
  {
    SEG S = Edge(poly, i);
    if (IsOnSeg(S, p))
    {
        return true;                 //如果想让 在poly上则返回 true,
    }
    if (!IsEqual(S.a.y, S.b.y))
    {
        POINT & q = (S.a.y > S.b.y)?(S.a):(S.b);
        if (IsOnSeg(L, q))
        {
          ++count;
        }
        else if (!IsOnSeg(L, S.a) && !IsOnSeg(L, S.b) && IsIntersect(S, L))
        {
          ++count;
        }
    }
  }
  return (count % 2 != 0);
}

int main()
{
    int m;
    double x[110],y[110];
    POLY area;
    POINT arrow;
    area.x = x;
    area.y = y;
    while(scanf("%d",&area.n)==1)
    {
        for (int i=0;i<area.n;i++) {
            scanf("%lf %lf",x+i,y+i);
        }
        x[i] = x[0];
        y[i] = y[0];
        scanf("%d",&m);
        for (i=0;i<m;i++) {
            scanf("%lf %lf",&arrow.x,&arrow.y);
            if (IsInPoly(area, arrow)) {
                printf("Yes\n");
            }
            else {
                printf("No\n");
            }
        }
    }
}