300468: CF89D. Space mines
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Space mines
题意翻译
很久以前,在遥远的银河系。。。 达斯·韦德发现了叛军基地的位置。现在他要用死星摧毁基地(以及基地所在的整个星球)。 当叛军得知死亡之星即将来临时,他们决定使用新的秘密武器——太空地雷。让我们来描述一下太空地雷阵的建造。 每个空间地雷的形状都像一个球(我们称之为雷体),半径r,中心在O点。几个尖从中心突出。每个尖可以表示为一个段,将矿中心与某个点P连接起来,这样(运输长尖头矿是有问题的),其中|OP|是连接O和P的线段的长度。用向量P来描述点P很方便,这样P=O+P。 死星的形状像一个半径为R的球(R超过任何地雷的半径)。它以等于∣v∣的速度沿v向量以恒定速度移动。在叛军注意到死星的那一刻,它位于A点。 叛军在死星的路上发现了n颗太空地雷。你可以认为这些地雷是闲置的。死星不知道地雷的存在,也无法注意到它们,这就是为什么它不改变它的运动方向。一旦死亡之星碰到地雷(它的身体或其中一个尖刺),地雷就会爆炸并摧毁死亡之星。触碰是指在太空中有一点同时属于地雷和死星的情况。人们认为,如果死星能够无限长时间地移动而不触碰地雷,它就不会被摧毁。 帮助叛军确定他们是否能成功地用太空地雷摧毁死星。如果他们成功了,就要确定它何时发生(从死星被发现的那一刻开始)。 ### 输入 第一行包含7个整数,它们是死星的初始位置、运动方向和半径。 第二行包含一个整数n,即地雷的数量(1<=n<=100 1<=n<=10)。接着是n个数据组合,第i数据组合对应第i地雷 每个数据组合包含描述第i个矿的尖峰,其中第j个描述第i个尖峰,包含3个整数p{ux},给定尖峰指向的向量的坐标。题目描述
Once upon a time in the galaxy of far, far away... Darth Wader found out the location of a rebels' base. Now he is going to destroy the base (and the whole planet that the base is located at), using the Death Star. When the rebels learnt that the Death Star was coming, they decided to use their new secret weapon — space mines. Let's describe a space mine's build. Each space mine is shaped like a ball (we'll call it the mine body) of a certain radius $ r $ with the center in the point $ O $ . Several spikes protrude from the center. Each spike can be represented as a segment, connecting the center of the mine with some point $ P $ , such that ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF89D/260097c7a43ccaae894b47162bab71c5ba9400fd.png) (transporting long-spiked mines is problematic), where $ |OP| $ is the length of the segment connecting $ O $ and $ P $ . It is convenient to describe the point $ P $ by a vector $ p $ such that $ P=O+p $ . The Death Star is shaped like a ball with the radius of $ R $ ( $ R $ exceeds any mine's radius). It moves at a constant speed along the $ v $ vector at the speed equal to $ |v| $ . At the moment the rebels noticed the Star of Death, it was located in the point $ A $ . The rebels located $ n $ space mines along the Death Star's way. You may regard the mines as being idle. The Death Star does not know about the mines' existence and cannot notice them, which is why it doesn't change the direction of its movement. As soon as the Star of Death touched the mine (its body or one of the spikes), the mine bursts and destroys the Star of Death. A touching is the situation when there is a point in space which belongs both to the mine and to the Death Star. It is considered that Death Star will not be destroyed if it can move infinitely long time without touching the mines. Help the rebels determine whether they will succeed in destroying the Death Star using space mines or not. If they will succeed, determine the moment of time when it will happen (starting from the moment the Death Star was noticed).输入输出格式
输入格式
The first input data line contains $ 7 $ integers $ A_{x},A_{y},A_{z},v_{x},v_{y},v_{z},R $ . They are the Death Star's initial position, the direction of its movement, and its radius ( $ -10<=v_{x},v_{y},v_{z}<=10 $ , $ |v|>0 $ , $ 0<R<=100 $ ). The second line contains an integer $ n $ , which is the number of mines ( $ 1<=n<=100 $ ). Then follow $ n $ data blocks, the $ i $ -th of them describes the $ i $ -th mine. The first line of each block contains $ 5 $ integers $ O_{ix},O_{iy},O_{iz},r_{i},m_{i} $ , which are the coordinates of the mine centre, the radius of its body and the number of spikes ( $ 0<r_{i}<100,0<=m_{i}<=10 $ ). Then follow $ m_{i} $ lines, describing the spikes of the $ i $ -th mine, where the $ j $ -th of them describes the $ i $ -th spike and contains $ 3 $ integers $ p_{ijx},p_{ijy},p_{ijz} $ — the coordinates of the vector where the given spike is directed (![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF89D/e15d6928125dbbd6d3db0eba4dcaa5f55ebb124f.png)). The coordinates of the mines' centers and the center of the Death Star are integers, their absolute value does not exceed $ 10000 $ . It is guaranteed that $ R>r_{i} $ for any $ 1<=i<=n $ . For any mines $ i≠j $ the following inequality if fulfilled: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF89D/c88573aa62fcdd898ca0b5d89890896a0c4700d4.png). Initially the Death Star and the mines do not have common points.
输出格式
If the rebels will succeed in stopping the Death Star using space mines, print the time from the moment the Death Star was noticed to the blast. If the Death Star will not touch a mine, print "-1" (without quotes). For the answer the absolute or relative error of $ 10^{-6} $ is acceptable.
输入输出样例
输入样例 #1
0 0 0 1 0 0 5
2
10 8 0 2 2
0 -3 0
2 2 0
20 0 0 4 3
2 4 0
-4 3 0
1 -5 0
输出样例 #1
10.0000000000
输入样例 #2
8 8 4 4 4 2 6
1
-2 -2 -1 3 0
输出样例 #2
-1
输入样例 #3
30 30 2 1 2 1 20
3
0 0 40 5 1
1 4 4
-10 -40 -5 7 0
100 200 95 8 1
-10 0 0
输出样例 #3
74.6757620881