SGU 110 Dungeon
一些球体，给了一个光线，求光线反射的顺序。
110. Dungeon
time limit per test: 0.25 sec. memory limit per test: 4096 KB
The mission of space explorers found on planet M the vast dungeon. One of the dungeon halls is fill with the bright spheres. The explorers find out that the light rays reflect from the surface of the spheres according the ordinary law (the incidence angle is equal to the reflectance angle, the incidence ray, the reflected ray and the perpendicular to the sphere surface lay in the one plane). The ancient legend says that if the light ray will reflect from the spheres in the proper order, than the door to the room with very precious ancient knowledge will open. You are not to guess the right sequence; your task is much simpler. You are given the positions and the radii of the spheres, the place where the laser shot was made and the direction of light propagation. And you must find out the sequence in which the light will be reflected from the spheres.
Input
The first line of input contains the single integer n (1≤n≤50) - the amount of the spheres. The next n lines contain the coordinates and the radii of the spheres xi, yi, zi, ri (the integer numbers less or equal to 10000 by absolute value). The last line contains 6 real numbers - the coordinates of two points. The first one gives the coordinates of the place of laser shot, and the second gives the direction in which it was made (the second point is the point on the ray). The starting point of the ray lies strictly outside of any sphere.
Output
Your program must output the sequence of sphere numbers (spheres are numbers from 1 as they was given in input), from which the light ray was reflected. If the ray will reflect more the 10 times, than you must output first 10, then a space and the word ‘etc.’ (without quotes). Notice: if the light ray goes at a tangent to the sphere you must assume that the ray was reflected by the sphere.
Sample Input 1
1
0 0 2 1
0 0 0 0 0 1
Sample Output 1
1
Sample Input 2
2
0 0 2 1
0 0 -2 1
0 0 0 0 0 100
Sample Output 2
1 2 1 2 1 2 1 2 1 2 etc.
按照点 和 方向向量去表示射线。 用参数方程去求解射线和球的交点，先找到一个最小的，然后进行反射。
/* ***
Author :kuangbin
Created Time :2014/8/4 22:01:33
File Name :E:\2014ACM\专题学习\计算几何\三维几何\SGU110.cpp
************************************************ */
#include <stdio.h>
#include <string.h>
#include
#include
#include
#include
#include
#include
#include
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const double eps = 1e-8;
int sgn(double x)
{
if(fabs(x) < eps)return 0;
if(x < 0)return -1;
else return 1;
}
struct Point3
{
double x,y,z;
Point3(double _x = 0,double _y = 0,double _z = 0)
{
x = _x;
y = _y;
z = _z;
}
void input()
{
scanf(“%lf%lf%lf”,&x,&y,&z);
}
double len()
{
return sqrt(x*x+y*y+zz);
}
double len2()
{
return x\x+y*y+zz;
}
double distance(const Point3 &b)const
{
return sqrt((x-b.x)(x-b.x)+(y-b.y)(y-b.y)+(z-b.z)(z-b.z));
}
Point3 operator -(const Point3 &b)const
{
return Point3(x-b.x,y-b.y,z-b.z);
}
Point3 operator +(const Point3 &b)const
{
return Point3(x+b.x,y+b.y,z+b.z);
}
Point3 operator (const double &k)const
{
return Point3(x\k,y*k,zk);
}
Point3 operator /(const double &k)const
{
return Point3(x/k,y/k,z/k);
}
double operator (const Point3 &b)const
{
return x*b.x+y*b.y+zb.z;
}
Point3 operator ^(const Point3 &b)const
{
return Point3(y\b.z-z*b.y,z*b.x+x*b.z,x*b.y-y*b.x);
}
};
//球体
struct Sphere
{
Point3 o;
double r;
void input()
{
o.input();
scanf(“%lf”,&r);
}
};
//射线和球求交点
bool Intersaction(Point3 st,Point3 dir,Sphere sp,double &t)
{
double a = dir.x*dir.x + dir.y*dir.y + dir.zdir.z;
double b = 2(st.x-sp.o.x)*dir.x + 2*(st.y-sp.o.y)*dir.y + 2*(st.z-sp.o.z)dir.z;
double c = (st.x-sp.o.x)(st.x-sp.o.x) + (st.y-sp.o.y)(st.y-sp.o.y) +
(st.z-sp.o.z)(st.z-sp.o.z) - sp.rsp.r;
double deta = b\b - 4*ac;
if(sgn(deta) < 0)return false;
double x1 = (-b-sqrt(deta))/(2a);
double x2 = (-b+sqrt(deta))/(2a);
if(x1 > x2)swap(x1,x2);
if(sgn(x1) <= 0)return false;
t = x1;
return true;
}
Point3 Ref(Point3 st,Point3 p,Sphere sp)
{
Point3 tp = sp.o + ( ((p-sp.o)((p-sp.o)(st-sp.o)))/((p-sp.o).len2()) );
return Point3(2\tp.x-st.x,2*tp.y-st.y,2*tp.z-st.z)-p;
}
Sphere sp[100];
int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int n;
while(scanf(“%d”,&n) == 1)
{
for(int i = 0;i < n;i++)sp[i].input();
Point3 now,dir;
now.input();
dir.input();
dir = dir - now;
int last = -1;
for(int i = 0;i < 11;i++)
{
int id = -1;
double mint = 1e300;
for(int j = 0;j < n;j++)
if(j != last)
{
double t;
if(Intersaction(now,dir,sp[j],t))
if(mint > t)
{
id = j;
mint = t;
}
}
if(id != -1)
{
if(i == 10)
{
printf(“ etc.\n”);
break;
}
if(i > 0)printf(“ “);
Point3 pp = now + (dir*mint);
Point3 tmp = Ref(now,pp,sp[id]);
now = pp;
dir = tmp;
printf(“%d”,id+1);
}
else
{
printf(“\n”);
break;
}
last = id;
}
}
return 0;
}
