HDU 3471 England vs Germany 【三维线段判定】

2010MU(ACM2010多校联合训练)-Fourth-UESTC-C Problem-England vs Germany-Solution Report

前言:这个2B题。谁出的谁自杀去。题目描述和数据还有官方解题报告都对着干。我们这帮做题的情何以堪!?

Description

 

The big fight between England and Germany was destroyed by the guy called Larrionda. England could have made a tie of 2:2. But that poor guy disqualified Lampard's wonderful goal. The ball passed through the goal line by half a meter, however, Larrionda turned a blind eye to this goal.

As a fan of Three Lion Regimen, silentsky want to develop a system which uses sensors to get the information to check if it scored or not.

 

The information includes a point as the location of ball, a vector as the velocity and a cuboid as the goal.

译文大意:

三狮军团和德意志战车单挑的时候,裁判拉里昂达2B了。因为拉里昂达的2B,那个完美进球被吹没了,本来有可能打平的比赛变成了日耳曼人屠戮了盎格鲁撒克逊人。

出题的人是个英粉,现在,他想让你编程构建一个系统来确定那个球到底是进还是没进。

所给信息包括,足球起始位置,速度矢量,以及,球门长方体八点。(均为三维坐标)

 

Input

The first line gives an integer t (t<=10000) indicating the number of test cases.

For each case:

The first line gives three real numbers x, y , z, indicating a point to represent the ball.

The second line gives three real numbers a, b, c. indicates a vector to represent the velocity.

The following 8 lines give 8 points according the sequence A, B, C, D, E, F, G, H as is shown in the figure.

 Absolute value of all real numbers are smaller than 10000.

 It is guaranteed that the initial location of the ball is not inside the goal.

 译文:

第一行为测试数据组数(小于等于10000的整数)。

第二行是球的坐标。

第三行是速度矢量。

第4~11行是按序给出的A~H八点的坐标。

(以上数据除组数外均为实数)

所有实数的绝对值均小于10000。

确保球的初始位置不在球门 (这句话是让无数人WA的关键。实际的测试数据中给出了在球门内的数据。)(怎么说呢。是写解题报告和出题的人没有和写标程测试数据的人统一好意见呢。还是根本就没认真对待出题这种神圣的事情,纯粹2B了呢?!)

(自己建的图,特意下载了个AutoCAD2010.花了一个小时玩明白一点点建了个图)

Output

 if it scored then output “Case X: Stupid Larrionda!!!”.otherwise output “Case X: Intelligent Larrionda!!!”.(X is the case number starting from 1).

 We consider ABCD as the front of the goal and AB,BC,CD,DA as the goalposts. A shoot scores if and only if it passes through the front of the goal and doesn't crash on the goalpost)

译文:如果球进了,我们就输出“Case X: Stupid Larrionda!!!”(第X种情况:愚蠢的拉里昂达!!!)否则就输出 “Case X: Intelligent Larrionda!!!”(第X种情况:聪明的拉里昂达!!!)(X从1开始计数)

(我们认为ABCD为球门,AB、BC、CD、DA为球门框,球进了的意思是,球从球门穿过并且未触碰到球门框。)

(可是扯淡的地方在于,门线竟然被当做了球门,我们很无奈,但是要尊重题意(去你妈的题意),没办法,还是把门线当做了门框。

这道题的关键就在于判断球是否从球门进入,而非从侧面或者背面或者上下面进入。)

(但是因为,球在球门内向球门里射这种情况的存在,使这道经典计算几何练习题变成了ws的扯淡题。下面将提到。)

Sample Input

1

20 0 5

-10 5 0

10 0 10

10 10 10

10 10 0

10 0 0

0 0 10

0 10 10

0 10 0

0 0 0

(模拟图在上面) 

Sample Output

Case 1: Stupid Larrionda!!!


题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3471

#include <iostream>
#include 
<cstring>
#include 
<cmath>
#include 
<cstdio>
#include 
<cctype>
#include 
<cstdlib>
#include 
<algorithm>
#include 
<vector>
#define MAX 1<<30
using namespace std;
const double eps=1e-8;
typedef 
long long ll;
int main()
{
    typedef 
struct
    {
    
double x;
    
double y;
    
double z;
    } plus; 
//三维点坐标的结构。。话说有没有这样的STL啊?
    plus r[100],xa[100],p[100];

//下面是我比赛的时候去恶补的高数知识。。下学期高数没学好啊。几何部分一窍不通。泪目。。。
   /* 面法向量(本题中简易做法是AEvector) 

   * 本题中因为给出的是严格长方体,所以ABCD面法向量就是AEvector

   * 下面的法向量求法就没用了,不过学会了更好,我这个数学2B
   * x0=(y2-y1)*(z3-z1)-(z2-z1)*(y3-y1),
   * y0=(z3-z1)*(x2-x1)-(x3-x1)*(z2-z1),
   * z0=(x2-x1)*(y3-y1)-(x3-x1)*(y2-y1)
   * x0*(x-x1)+y0(y-y1)+z0(z-z1)=0

   * 直线参数方程是本题中判断球所在位置的关键
   * 直线参数方程 (p为始点,f为末点,即交点)
   * xf=xp+mt
   * yf=yp+nt
   * zf=zp+qt

   * 以下为求参数方程中t的关键
   * 线面相交方程
   * x0*(xp+mt-x1)+y0*(yp+nt-y1)+z0*(zp+qt-z1)=0
   * (x0*m+y0*n+z0*q)t=(x1-xp)*x0+(y1-yp)*y0+(z1-zp)*z0
   * 参数解法(即,交点确定方法) 
*/
  
   
//  freopen("eg.in","r",stdin);
   
//  freopen("fuck3.out","w",stdout);
   int t,i,j,k,ca=0;
   
double temp[6],pp[100];//,r[4],l;
   plus o,v,m,f;
   scanf(
"%d",&t);
   
while(t--)
   {
    scanf(
"%lf%lf%lf",&o.x,&o.y,&o.z);
    scanf(
"%lf%lf%lf",&v.x,&v.y,&v.z);
    printf(
"Case %d: ",++ca);
    
for(i=0;i<8;i++)
     scanf(
"%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z);
    m.x
=p[4].x-p[0].x;
    m.y
=p[4].y-p[0].y;
    m.z
=p[4].z-p[0].z; //AEvector

    
//将AEvector与速度矢量进行点积,判断速度与法向量是否同向

    
//从而判断球是否射向球门内
    if(m.x*v.x+m.y*v.y+m.z*v.z<=eps)
     {
      printf(
"Intelligent Larrionda!!!\n");
      
continue;
     }

    
//求由球点与速度矢量确定的直线方程与ABCD及EFGH面的交点

    
//temp[0]为与ABCD的交点的参数t的值

    
//temp[1]为与EFGH的交点的参数t的值 
    temp[0=( (p[0].x-o.x)*m.x+(p[0].y-o.y)*m.y+(p[0].z-o.z)*m.z )/(m.x*v.x+m.y*v.y+m.z*v.z);
    temp[
1=( (p[4].x-o.x)*m.x+(p[4].y-o.y)*m.y+(p[4].z-o.z)*m.z )/(m.x*v.x+m.y*v.y+m.z*v.z);

    
/*判断球是否在球网EFGH的后面

    * 本来我只判断了球是否在球门之后,毕竟题目里说了球初始点不可能在球门内

    * 可是我事后去翻看了标程以及标程数据生成器,果然有这样的数据存在

    * 所以一开始sunyuqi和linyiyong同学竟然能把这道题过了,我表示非常震惊

    * 他们这叫歪打正着呢?还是有先见之明?

    * 学长们,以及我,都被那组不符合题意的数据卡死了。10+的WA。光辉的一B啊!

    * 1W组数据中的100组。被那2B的标程搞死。NND。

    
*/
    
if(temp[0]<=eps&&temp[1]<=eps)
     {
      printf(
"Intelligent Larrionda!!!\n");
      
continue;
     }

    
//前面一路判断都为真的话,则求ABCD与射球轨迹的交点
    f.x = o.x + temp[0]*v.x;
    f.y 
= o.y + temp[0]*v.y;
    f.z 
= o.z + temp[0]*v.z;

    
/*

    * 现在判断交点是否在ABCD面内

    *(严格内部,而非在这个平面上,但不在所包围的区域内)

    * 想法是,求出FAvector,FBvector,FCvector,FDvector(交点在F)

    * 再顺时针对这四个矢量求叉积,叉积即该平面(ABCD)的一侧法向量

    * 再判断这四个法向量是否在同侧即可

    * 判断方法为这四个叉积所得向量进行顺时针点积。均为正,则同向。

    
*/
    
for(i=0;i<4;i++)
    {
     r[i].x 
= p[i].x - f.x;
     r[i].y 
= p[i].y - f.y;
     r[i].z 
= p[i].z - f.z;
    }
    
for(i=0;i<3;i++)
    {
     xa[i].x
= r[i+1].z*r[i].y-r[i+1].y*r[i].z;
     xa[i].y
= r[i+1].x*r[i].z-r[i+1].z*r[i].x;
     xa[i].z
= r[i+1].y*r[i].x-r[i+1].x*r[i].y;
    }
    xa[
3].x=-( r[3].z*r[0].y-r[3].y*r[0].z);
    xa[
3].y=-( r[3].x*r[0].z-r[3].z*r[0].x);
    xa[
3].z=-( r[3].y*r[0].x-r[3].x*r[0].y);
    
for(i=0;i<3;i++)
     {
      
if(xa[i].x*xa[i+1].x+xa[i].y*xa[i+1].y+xa[i].z*xa[i+1].z>0);
      
else
       {printf(
"Intelligent Larrionda!!!\n");break;}
     }
     
if(i==3)
      printf(
"Stupid Larrionda!!!\n");
   }
   
//  system("pause");
   
//   fclose(stdin);
   
//  fclose(stdout);
   return 0;
}
/* 本题,我中间错了无数次。

 * 算法一改再改,从一开始判断球与球门的相对位置时计算点面距离,到中间的通过叉积矢量xyz坐标单纯相加判断是否同向,本人对高数以及计算几何进行了各种各样的练习。

 * 这还不算上,对于测试文件输入输出的学习,对于标程与自己程序对拍方法的学习。

 * 这道题消耗了我一天的时间,但是我觉得值,因为我深入理解了这个问题。虽然不代表我以后遇到这类问题能照AC不误,但至少,我从中收获了不少东西。

 * 顺便鄙视一下某些出题人。

 * 另外,本人的队友sunyuqi同学,做这题时运用了三维矩阵坐标变换的方法,鉴于本人线性代数超烂,故没学会,也就不摆上来献丑了。等以后学会了再来研究一下不迟。

 * 第一次写解题报告,如有错误,烦请指正。

 * 感谢各位百忙之中浏览本文。

 

 
*/

posted on 2011-07-05 13:08 BUPT-[aswmtjdsj] @ Penalty 阅读(471) 评论(1)  编辑 收藏 引用 所属分类: 计算几何HDU Solution Report


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年7月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿(1)

随笔分类(150)

随笔档案(71)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜