ZOJ1081 Points Within

PS: 判断点是否在多边形内，用的绕圈法，具体参见刘汝佳的训练指南。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; struct point { int x, y; point(double x=0, double y=0):x(x),y(y) {} }; point operator - (point A, point B) { return point(A.x-B.x, A.y-B.y); } double Cross(point A, point B) { return A.x*B.y - A.y*B.x; } vector
        
          v; vector
         
           Contain; vector
          
            check; int n, m; const double eps = 1e-10; int dcmp(double x) { if(fabs(x)
           
            0 && d1<=0 && d2 > 0) wn++; if(k<0 && d2<=0 && d1 > 0) wn--; } if(wn!=0) return 1; else return 0; } int main() { int T = 1; point tmp; bool first = false; while(scanf("%d", &n)!=EOF && n) { if(first) printf("\n"); else first = true; scanf("%d", &m); v.clear(); Contain.clear(); for(int i = 0; i < n; i++) { scanf("%d%d", &tmp.x, &tmp.y); Contain.push_back(tmp); } for(int i = n-1; i >= 0; i--) { v.push_back(Contain[i]); } check.clear(); for(int i = 0; i < m; i++) { scanf("%d%d", &tmp.x, &tmp.y); check.push_back(tmp); } printf("Problem %d:\n", T++); for(int i = 0; i < m; i++) { int res = isPointIn(check[i]); if(res==1) printf("Within\n"); else printf("Outside\n"); } } }