CF89D.Space mines

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

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 rr with the center in the point OO . Several spikes protrude from the center. Each spike can be represented as a segment, connecting the center of the mine with some point PP , such that (transporting long-spiked mines is problematic), where OP|OP| is the length of the segment connecting OO and PP . It is convenient to describe the point PP by a vector pp such that P=O+pP=O+p .

The Death Star is shaped like a ball with the radius of RR ( RR exceeds any mine's radius). It moves at a constant speed along the vv vector at the speed equal to v|v| . At the moment the rebels noticed the Star of Death, it was located in the point AA .

The rebels located nn 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 77 integers Ax,Ay,Az,vx,vy,vz,RA_{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<=vx,vy,vz<=10-10<=v_{x},v_{y},v_{z}<=10 , |v|>0 , 0<R<=100 ).

The second line contains an integer nn , which is the number of mines ( 1<=n<=1001<=n<=100 ). Then follow nn data blocks, the ii -th of them describes the ii -th mine.

The first line of each block contains 55 integers Oix,Oiy,Oiz,ri,miO_{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 mim_{i} lines, describing the spikes of the ii -th mine, where the jj -th of them describes the ii -th spike and contains 33 integers pijx,pijy,pijzp_{ijx},p_{ijy},p_{ijz} — the coordinates of the vector where the given spike is directed ().

The coordinates of the mines' centers and the center of the Death Star are integers, their absolute value does not exceed 1000010000 . It is guaranteed that R>r_{i} for any 1<=i<=n1<=i<=n . For any mines iji≠j the following inequality if fulfilled: . 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 10610^{-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
首页