学步园

一、判断两封闭单连通图形A和B关系：
　　旋转法：取图形A内的任一点X，如果X是B内部的点，则说明A、B相交。否则，连接X和B的边界上点P作线段XP。从X出发，考察从线段XP，作状态(I_A,I_B)，I_A和I_B非零与否分别表示在A和B的内部与否，初始时为(1, 0)，经过A或B的边界分别使IA或IB翻转，如果出现(I_A,I_B)=(1,1)就说明A、B相交，否则说明A、B不相交。
二、判断一个点X是否在N边形内部：
　　圆环染色法：以X为起点，多边形各端点P_i为终点得向量XP_i(i=0,1,...,N-1)。此后顺序考察各向量过程中，用到两个运算：以内角为准，到对比向量va相对于vb是顺时针还是逆时针的运算，返回1代表顺时针，-1表示逆时针，该运算可用向量积实现；三向量中间向量是否在两侧向量所夹内角中的判断，记作cr，可用解析法实现。记向量组XP_i为v[i]。算法如下（经初步验证）：   
　　bool inpvec(const vector *v, int n)
　　{
　　  int cl;
　　  int s = 0;
　　  int i, p;
　　  for(i = 2, p = 1; i < n; i++)
　　    if(cr(v, i, p, s)) p++;
　　  return check(v, p, s);
　　}
　　
　　bool cr(const vector *v, int ic, int io, int &s)
　　{
　　  int g1 = v[ic].x * v[io].y - v[ic].y * v[io].x;
　　  int g2 = (v[ic].x - v[io].x) * v[0].y - (v[ic].y - v[io].y) * v[0].x;
　　  if(g1 < 0 && g2 >= 0 || g1 > 0 && g2 <= 0) return true;
　　  if(g1 == 0) return false;
　　
　　  int dxc = v[ic].x * g2 - v[0].x * g1;
　　  int dxo = v[io].x * g2 - v[0].x * g1;
　　  int dyc = v[ic].y * g2 - v[0].y * g1;
　　  int dyo = v[io].y * g2 - v[0].y * g1;
　　
　　  if(dxc < 0 && dxo > 0 || dxc > 0 && dxo < 0 || 
　　      dyc < 0 && dyo > 0 || dyc > 0 && dyo < 0)
　　    s += (g1 > 0)? 1 : -1;
　　
　　  return ((dxc != 0 || dyc != 0) && (dxo != 0 || dyo != 0));
　　}
　　
　　bool check(const vector *v, int p, int s)
　　{
　　  int g1 = v[1].x * v[0].y - v[1].y * v[0].x;
　　  int g2 = v[0].x * v[p].y - v[0].y * v[p].x;
　　  bool sd = (g1 > 0 && g2 > 0) || (g1 < 0 && g2 < 0);
　　  return (s == 0 && sd ||s != 0 && !sd);
　　}