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
|