判断一个点是否在多边形内

  1 /*
  2 fzu_1120
  3 判断点q是否在多边形内的一种方法，过q作水平射线L，
  4 如果L与多边形P的边界不相交，则q在P的外部。否则，
  5 L和P的边界相交，具体地说，交点个数为奇（偶）数
  6 时，点q在P的内（外）部。 */
  7 
  8 #include <stdio.h>
  9 #include <stdlib.h>
 10 #include <math.h>
 11 
 12 #define MaxNode 50
 13 #define INF  999999999
 14 
 15 typedef struct TPoint
 16 {
 17     double x;
 18     double y;    
 19 }TPoiont;
 20 
 21 typedef struct TSegment
 22 {
 23     
 24     TPoint p1;
 25     TPoint p2;
 26 }TSegment;
 27 
 28 typedef struct TPolygon
 29 {
 30     TPoint point[MaxNode];
 31     int n;
 32 }TPolygon;
 33 
 34 double multi(TPoint p1, TPoint p2, TPoint p0)
 35 {
 36     //求矢量[p0, p1], [p0, p2]的叉积
 37     //p0是顶点 
 38     return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
 39     //若结果等于0，则这三点共线
 40     //若结果大于0，则p0p2在p0p1的逆时针方向
 41     //若结果小于0，则p0p2在p0p1的顺时针方向 
 42 }
 43 
 44 double max(double x, double y)
 45 {
 46     //比较两个数的大小，返回大的数
 47     if(x > y) return x;
 48     else return y; 
 49 }
 50 
 51 double min(double x, double y)
 52 {
 53     //比较两个数的大小，返回小的数
 54     if(x < y) return x;
 55     else return y; 
 56 }
 57 
 58 bool Intersect(TSegment L1, TSegment L2)
 59 {
 60     //线段l1与l2相交而且不在端点上时，返回true    
 61     //判断线段是否相交
 62     //1.快速排斥试验判断以两条线段为对角线的两个矩形是否相交 
 63     TPoint s1 = L1.p1;
 64     TPoint e1 = L1.p2;
 65     TPoint s2 = L2.p1;
 66     TPoint e2 = L2.p2;
 67     //2.跨立试验
 68     if(
 69         (max(s1.x, e1.x) > min(s2.x, e2.x)) &&
 70         (max(s2.x, e2.x) > min(s1.x, e1.x)) &&
 71         (max(s1.y, e1.y) > min(s2.y, e2.y)) &&
 72         (max(s2.y, e2.y) > min(s1.y, e1.y)) &&
 73         (multi(s2, e1, s1) * multi(e1, e2, s1) > 0) &&
 74         (multi(s1, e2, s2) * multi(e2, e1, s2) > 0)
 75         )  return true;
 76     
 77     return false;    
 78 }
 79 
 80 
 81 bool Online(TSegment L, TPoint p)
 82 {
 83     //p在L上(不在端点)时返回true
 84     //1.在L所在的直线上 
 85     //2.在L为对角线的矩形中
 86     double dx, dy, dx1, dy1;
 87     dx = L.p2.x - L.p1.x;
 88     dy = L.p2.y - L.p1.y;
 89     dx1 = p.x - L.p1.x;
 90     dy1 = p.y - L.p1.y;
 91     if(dx * dy1 - dy * dx1 != 0) return false; //叉积
 92     if(dx1 * (dx1 - dx) < 0 || dy1 * (dy1 - dy) < 0) return true;
 93     return false; 
 94 }
 95 
 96 bool same1(TSegment L, TPoint p1, TPoint p2)
 97 {
 98     //判断p1, p2是否在L的同侧 
 99     if(multi(p1, L.p2, L.p1) * multi(L.p2, p2, L.p1)< 0) return true;
100     return false;    
101 }
102 
103 bool Inside(TPoint q, TPolygon polygon)
104 {
105     int c, i;
106     TSegment L1, L2;
107     c = 0;
108     L1.p1 = q;
109     L1.p2 = q;
110     L1.p2.x = INF; 
111     /*
112     （1）相交 
113     1.p[i]和p[i+1]在L的两侧 
114     2.p[i]和p[i+2]在L的同侧
115     3.p[u]和p[i+3]在L的同侧或异侧 
116     */
117     for(i = 0;i <= polygon.n - 1;i++){
118         L2.p1 = polygon.point[i];
119         L2.p2 = polygon.point[(i + 1) % polygon.n];
120         if(Intersect(L1, L2)){
121             c++; 
122             continue;
123         }
124         if(!Online(L1, polygon.point[(i + 1) % polygon.n])) continue; 
125         if(!Online(L1, polygon.point[(i + 2) % polygon.n]) && 
126             !same1(L1, polygon.point[i], polygon.point[(i + 2) % polygon.n])){
127             c++;
128             continue;
129         }
130         if(Online(L1, polygon.point[(i + 2) % polygon.n]) && 
131             !same1(L1, polygon.point[i], polygon.point[(i + 3) % polygon.n]))
132             c++;
133     }  
134     if(c % 2 == 0) return false;
135     else return true;
136 }
137 
138 int main()
139 {
140     int i, test, k;
141     int primp, primq;
142     TPoint p;
143     p.x = 0;
144     p.y = 0;
145     test = 1;
146     TPolygon polygon;
147     while(scanf("%d", &polygon.n) != EOF && polygon.n){
148         printf("Pilot %d
", test++);
149         for(i = 0;i <= polygon.n - 1;i++){
150             scanf("%lf%lf", &polygon.point[i].x, &polygon.point[i].y);
151         }
152         scanf("%d%d", &primp, &primq);
153         if(Inside(p, polygon)){
154             printf("The pilot is in danger!
");
155             k = (primp - 1) * (primq - 1) / 2;
156             printf("The secret number is %d.
", k); 
157         }
158         else printf("The pilot is safe.
");
159         printf("
");
160     }
161     return 0;
162 }