计算几何点与多边形的位置判断zoj1081Points Within

This article is made by Jason-Cow.
Welcome to reprint.
But please post the writer's address.

http://www.cnblogs.com/JasonCow/

叉积判方向

点积判角度

角度和=0°在外面

否则在里面

AC Code 这么短的计算几何，君难道不想收入囊中吗？

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define sqr(x) ((x)*(x))
#define RG register
#define op operator
#define IL inline
#define db double
#define bl bool
const db pi=acos(-1.0),eps=1e-10;
struct D{db x,y;D(db x=0.0,db y=0.0):x(x),y(y){}};
typedef D V;
V operator+(V A,V B){return V(A.x+B.x,A.y+B.y);}
V operator-(V A,V B){return V(A.x-B.x,A.y-B.y);}
V operator*(V A,db N){return V(A.x*N,A.y*N);}
V operator/(V A,db N){return V(A.x/N,A.y/N);}
V Rotate(V A,db a){return V(A.x*cos(a)-A.y*sin(a),A.x*sin(a)+A.y*cos(a));}
int dcmp(db x){if(fabs(x)<eps)return 0;else return x>0?1:-1;}
bl OnSegment(D A,D B,D P){return dcmp((P.x-A.x)*(P.x-B.x))<=0&&dcmp((P.y-A.y)*(P.y-B.y))<=0;}
db Len(D A){return sqrt(A.x*A.x+A.y*A.y);}
db Cross(V A,V B){return A.x*B.y-A.y*B.x;}
db Dot(V A,V B){return A.x*B.x+A.y*B.y;}
db VectorAngle(V a,V b){return acos(Dot(a,b)/(Len(a)*Len(b)));}

bl InPolygon(D P,D*R,int n){
  db ans=0.0;
  R[0]=R[n];
  for(int i=0;i<n;i++){
    D A=R[i],B=R[i+1];
    int cross=dcmp(Cross(A-P,B-P));
    if(cross==0){if(OnSegment(A,B,P))return true;}
    else{
      db angle=VectorAngle(A-P,B-P);
      ans+=(cross>0?angle:-angle);
    }
  }
  return dcmp(ans)!=0;
}
const int maxn=(int)1e5+10;
D A[maxn];

int main(){    
  int n,m,cnt=0;
  db a,b;
  while(scanf("%d",&n)&&n){
    if(cnt!=0)puts("");
    printf("Problem %d:\n",++cnt);
    scanf("%d",&m);
    for(int i=1;i<=n;i++)scanf("%lf%lf",&A[i].x,&A[i].y);
    for(int i=1;i<=m;i++){
      scanf("%lf%lf",&a,&b);
      printf("%s\n",InPolygon(D(a,b),A,n)?"Within":"Outside");
    }
  }
  return 0;
}