#include #include #define ERROR 1 #define X 0 #define Y 1 typedef enum { FALSE, TRUE } bool; typedef enum { Pin, Qin, Unknown } tInFlag; #define DIM 2 /* Dimension of points */ typedef int tPointi[DIM]; /* type integer point */ typedef double tPointd[DIM]; /* type double point */ #define PMAX 1000 /* Max # of pts in polygon */ typedef tPointi tPolygoni[PMAX];/* type integer polygon */ int Area2( tPointi a, tPointi b, tPointi c ); void SubVec( tPointi a, tPointi b, tPointi c ); int Dot( tPointi a, tPointi b ); bool LeftOn( tPointi a, tPointi b, tPointi c ); bool Left( tPointi a, tPointi b, tPointi c ); void PrintPoly( int n, tPolygoni P ); void PrintPoint( tPointi p ); void PrintPointd( tPointd p ); void ConvexIntersect( tPolygoni P, tPolygoni Q, int n, int m ); tInFlag InOut( tPointd p, tInFlag inflag, bool aHB, bool bHA ); int Advance( int a, int *aadv, int n, bool inside, tPointi v ); bool Intersection( tPointi a, tPointi b, tPointi c, tPointi d, tPointd p ); bool EqPoint( tPointi a, tPointi b ); int n, m, pom; tPolygoni P, Q; double s,t; main() { n = ReadPoly( P ); m = ReadPoly( Q ); ConvexIntersect( P, Q, n, m ); } void ConvexIntersect( tPolygoni P, tPolygoni Q, int n, int m ) /* P has n vertices, Q has m vertices. */ { int a, b; /* indices on P and Q (resp.) */ int a1, b1; /* a-1, b-1 (resp.) */ tPointi A, B; /* directed edges on P and Q (resp.) */ int cross; /* A x B */ bool bHA, aHB; /* b in H(A); a in H(b). */ tPointi Origin = {0,0}; /* (0,0) */ tPointi r; tPointd p; /* double point of intersection */ tInFlag inflag; /* {Pin, Qin, Unknown}: which polygon is known to be inside */ int i; /* loop counter */ int aadv, badv; /* # advances on a & b indices (from first intersection) */ double pom2; /* Initialize variables. */ a = 0; b = 0; aadv = 0; badv = 0; i = 0; pom = 0; inflag = Unknown; do { /* Computations of key variables. */ a1 = (a + n - 1) % n; b1 = (b + m - 1) % m; SubVec( P[a], P[a1], A ); SubVec( Q[b], Q[b1], B ); cross = Area2( Origin, A, B ); bHA = Left( P[a1], P[a], Q[b] ); aHB = Left( Q[b1], Q[b], P[a] ); /*printf("a=%d, b=%d, bHA=%d, aHB=%d, cross=%d\n", a, b, bHA, aHB, cross);*/ /* If A & B intersect, update inflag. */ if ( Intersection( P[a1], P[a], Q[b1], Q[b], p ) ) { /* printf("Intersection:P[%d][%d], Q[%d][%d]\n", a1,a,b1,b); */ if ( inflag == Unknown ) { aadv = 0; badv = 0; } inflag = InOut( p, inflag, aHB, bHA ); /*printf("inflag=%d\n",inflag);*/ } /* Advance rules. */ if ( (cross == 0) && !bHA && !aHB ) { if ( inflag == Pin ) b = Advance( b, &badv, m, inflag == Qin, Q[b] ); else a = Advance( a, &aadv, n, inflag == Pin, P[a] ); /*printf("Collinear: now a=%d, b=%d\n",a,b);*/ } else if ( cross >= 0 ) if ( bHA ) a = Advance( a, &aadv, n, inflag == Pin, P[a] ); else { b = Advance( b, &badv, m, inflag == Qin, Q[b] ); } else if ( cross < 0 ){ if ( aHB ) b = Advance( b, &badv, m, inflag == Qin, Q[b] ); else a = Advance( a, &aadv, n, inflag == Pin, P[a] ); } /* Quit when both indices have cycled, or one has cycled twice. */ /*printf("aadv=%d, badv=%d\n", aadv, badv);*/ } while ( !( ( (aadv >= n) && (badv >= m) ) || (aadv >= 2*n) || (badv >= 2*m) ) ); /* Deal with special cases: not implemented here. */ if ( inflag == Unknown) { i=0;pom2=0.0;r[0]=P[0][0]+3;r[1]=P[0][1]; while ((i=0.0) && (t<1.0)){ if(pom2!=0.0){if(pom2*s<0.0){inflag=Pin;}} else{pom2=s;}}} ++i; } i=0;pom2=0.0;r[0]=Q[0][0]+3;r[1]=Q[0][1]; while((i=0.0) && (t<1.0)){ if(pom2!=0.0){if(pom2*s<0.0){inflag=Qin;}} else{pom2=s;}}} i++;} if(inflag==Pin){printf("1\n");} else {if(inflag==Qin){printf("2\n");} else{printf("3\n");}} } } /* Prints out the double point of intersection, and toggles in/out flag. */ tInFlag InOut( tPointd p, tInFlag inflag, bool aHB, bool bHA ) { PrintPointd( p ); /* putchar('\n'); */ /* Update inflag. */ if ( aHB ) return Pin; else if ( bHA ) return Qin; } /* Advances and prints out an inside vertex if appropriate. */ int Advance( int a, int *aadv, int n, bool inside, tPointi v ) { if ( inside ) { PrintPoint( v );/* putchar('\n');*/ } (*aadv)++; return (a+1) % n; } bool Intersection( tPointi a, tPointi b, tPointi c, tPointi d, tPointd p ) { double denom; /* Denoninator of solutions. */ s=0.0;t=0.0; denom = a[0] * ( d[1] - c[1] ) + b[0] * ( c[1] - d[1] ) + d[0] * ( b[1] - a[1] ) + c[0] * ( a[1] - b[1] ); /* If denom is zero, then the line segments are parallel. */ /* In this case, return false even though the segments might overlap. */ if (denom == 0.0) return FALSE; s = ( a[0] * ( d[1] - c[1] ) + c[0] * ( a[1] - d[1] ) + d[0] * ( c[1] - a[1] ) ) / denom; t = -( a[0] * ( c[1] - b[1] ) + b[0] * ( a[1] - c[1] ) + c[0] * ( b[1] - a[1] ) ) / denom; p[0] = a[0] + s * ( b[0] - a[0] ); p[1] = a[1] + s * ( b[1] - a[1] ); /*printf("Intersection:s=%10.6f,t=%10.6f\n", s, t );*/ if ( (0.0 < s) && (s < 1.0) && (0.0 < t) && (t < 1.0) ) return TRUE; else if ( ((s == 0.0) && (0 <= t) && (t <= 1.0)) || ((t == 0.0) && (0 <= s) && (s <= 1.0)) ) return TRUE; else return FALSE; } /* Implements a = b, assignment of points/vectors. Assignment between arrays is not possible in C. */ void PointAssign( tPointi a, tPointi b ) { int i; for ( i = 0; i < DIM; i++ ) a[i] = b[i]; } void PrintPoint( tPointi p ) { int i; pom++; for ( i = 0; i < DIM; i++ ) { printf(" %d", p[i]); } putchar('\n'); } void PrintPointd( tPointd p ) { int i; if(pom==0){printf("0\n");} pom++; for ( i = 0; i < DIM; i++ ) { printf("%5.2f", p[i]); } putchar('\n'); } /* Reads in the coordinates of the vertices of a polygon from stdin, puts them into P, and returns n, the number of vertices. Formatting conventions: etc. */ int ReadPoly( tPolygoni P ) { int n = 0; int nin; scanf("%d", &nin); /* printf("Polygon:\n"); printf(" i x y\n"); */ while ( (n < nin) && (scanf("%d %d",&P[n][0],&P[n][1]) != EOF) ) { /* printf("%3d%4d%4d\n", n, P[n][0], P[n][1]); */ ++n; } /* if (n < PMAX) printf("n = %3d vertices read\n",n); else printf("Error in read_poly: too many points; max is %d\n", PMAX); putchar('\n'); */ return n; } void PrintPoly( int n, tPolygoni P ) { int i; printf("Polygon:\n"); printf(" i l x y\n"); for( i = 0; i < n; i++ ) printf("%3d%4d%4d%4d\n", i, P[i][0], P[i][1]); } /* Returns true iff c is strictly to the left of the directed line through a to b. */ bool Left( tPointi a, tPointi b, tPointi c ) { return Area2( a, b, c ) > 0; } bool LeftOn( tPointi a, tPointi b, tPointi c ) { return Area2( a, b, c ) >= 0; } bool Collinear( tPointi a, tPointi b, tPointi c ) { return Area2( a, b, c ) == 0; } /* Puts a - b into c. */ void SubVec( tPointi a, tPointi b, tPointi c ) { int i; for( i = 0; i < DIM; i++ ) c[i] = a[i] - b[i]; } /* Returns twice the signed area of the triangle determined by a,b,c, positive if a,b,c are oriented ccw, and negative if cw. */ int Area2( tPointi a, tPointi b, tPointi c ) { return a[0] * b[1] - a[1] * b[0] + a[1] * c[0] - a[0] * c[1] + b[0] * c[1] - c[0] * b[1]; } bool EqPoint( tPointi a, tPointi b ) { int i; for ( i = 0; i < DIM; i++ ) if ( a[i] != b[i]) return FALSE; return TRUE; }