http://acm.hdu.edu.cn/showproblem.php?pid=3471
此题主要有两个问题:直线与面的交点,点是否在多边形内
对于速度V的方向有三种情况,可用V与ABCD面法向量的点积判断: 1 V指向ABCD面外侧,不可能进球; 2 V与ABCD面平行,不可能进球; 3 V指向ABCD面内侧,可能进球,分三种情况: 3.1 P在ABCD面内侧,不可能进球; 3.2 P在ABCD面上,当且仅当 P在多边形ABCD内(不包括边界)才进球 3.3 P在ABCD面外侧,当且仅当 直线P+xV与ABCD面的交点Q在多边形ABCD内(不包括边界)才进球
或者:Q=P+xV为与ABCD面交点,当且仅当 x>=0 && Q在ABCD面内才进球
hdu 3471 1#include <cstdio> 2#include <iostream> 3#include <cmath> 4#include <complex> 5#include <algorithm> 6#include <cstring> 7#include <queue> 8using namespace std; 9 10struct point 11{ 12 double x, y, z; 13 point( double a, double b, double c ) : x(a), y(b), z(c){ } 14 point( ){ x = 0, y = 0, z = 0; } 15}; 16const double eps = 1e-8; 17point operator ^ ( point a, point b ) 18{ 19 return point( b.z * a.y - b.y * a.z, b.x * a.z - a.x * b.z, a.x * b.y - b.x * a.y ); 20} 21double operator & ( point a, point b ) 22{ 23 return a.x * b.x + a.y * b.y + a.z * b.z; 24} 25point operator + ( point a, point b ) 26{ 27 return point( a.x + b.x, a.y + b.y, a.z + b.z ); 28} 29point operator - ( point a, point b ) 30{ 31 return point( a.x - b.x, a.y - b.y, a.z - b.z ); 32} 33point operator * ( point p, double x ) 34{ 35 return point( p.x * x, p.y * x, p.z * x ); 36} 37point operator / ( point p, double x ) 38{ 39 return point( p.x / x, p.y / x, p.z / x ); 40} 41double dis( point p1 ) 42{ 43 return sqrt(p1.x*p1.x+p1.y*p1.y+p1.z*p1.z); 44} 45int dblcmp( double x ) { return x < -eps ? -1 : x >eps ; } 46int main(int argc, char *argv[]) 47{ 48 int t; 49 //freopen("eg.in","r",stdin); 50 //freopen("out.txt","w",stdout); 51 scanf("%d",&t); 52 point v, s, p[8]; 53 for( int q = 1; q <= t; q++ ) 54 { 55 bool flag; 56 scanf("%lf%lf%lf",&s.x,&s.y,&s.z); 57 scanf("%lf%lf%lf",&v.x,&v.y,&v.z); 58 for( int i = 0; i < 8; i++ ) 59 scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z); 60 // 平面ABCD的法向量 61 point n = p[4] - p[0]; 62 if( dblcmp( v & n ) <= 0 ) 63 printf("Case %d: Intelligent Larrionda!!!\n",q); 64 else 65 { 66 double nlen = dis( n ); 67 double h1 = ( ( p[0] - s ) & n ) / nlen; 68 double h2 = ( v & n ) / nlen; 69 point t; 70 if( dblcmp( h1 ) > 0 ) t = s + v * h1 / h2; 71 else t = s; 72 flag = true; 73 for( int i = 0; i < 4; i++ ) 74 { 75 point c = p[(i+1)%4] - p[i]; 76 point d = t - p[i]; 77 point e = p[i] - t; 78 point f = p[(i+1)%4] - t; 79 if( ( dblcmp( dis( c ^ d ) ) == 0 ) && dblcmp( e & f ) <= 0 ) 80 flag = false; 81 } 82 if( !flag ) 83 { 84 printf("Case %d: Intelligent Larrionda!!!\n",q); 85 continue; 86 } 87 point g = p[2] - p[3]; 88 point h = p[0] - p[3]; 89 point tt = t - p[3]; 90 point j = p[0] - p[1]; 91 point k = p[2] - p[1]; 92 point ss = t - p[1]; 93 //double hlen = dis( p[0] - p[3] ), glen = dis( p[2] - p[3] ); 94 //double Hlen, Glen; 95 if( ( dblcmp( tt & h ) > 0 && dblcmp( tt & g ) > 0 ) && 96 ( dblcmp( ss & j ) > 0 && dblcmp( ss & k ) > 0 ) ) 97 printf("Case %d: Stupid Larrionda!!!\n",q); 98 else printf("Case %d: Intelligent Larrionda!!!\n",q); 99 } 100 } 101 return 0; 102} 103
|