CF28E.DravDe saves the world

省选/NOI-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

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

题目描述

How horrible! The empire of galactic chickens tries to conquer a beautiful city "Z", they have built a huge incubator that produces millions of chicken soldiers a day, and fenced it around. The huge incubator looks like a polygon on the plane Oxy with n vertices. Naturally, DravDe can't keep still, he wants to destroy the chicken empire. For sure, he will start with the incubator.

DravDe is strictly outside the incubator's territory in point A(x__a, y__a), and wants to get inside and kill all the chickens working there. But it takes a lot of doing! The problem is that recently DravDe went roller skating and has broken both his legs. He will get to the incubator's territory in his jet airplane LEVAP-41.

LEVAP-41 flies at speed V(x__v, y__v, z__v). DravDe can get on the plane in point A, fly for some time, and then air drop himself. DravDe is very heavy, that's why he falls vertically at speed F__down, but in each point of his free fall DravDe can open his parachute, and from that moment he starts to fall at the wind speed U(x__u, y__u, z__u) until he lands. Unfortunately, DravDe isn't good at mathematics. Would you help poor world's saviour find such an air dropping plan, that allows him to land on the incubator's territory? If the answer is not unique, DravDe wants to find the plan with the minimum time of his flight on the plane. If the answers are still multiple, he wants to find the one with the minimum time of his free fall before opening his parachute

多么可怕!银河系鸡帝国企图征服一座美丽的城市“Z”,它们建造了一座庞大的孵化器,每天生产数以百万计的鸡战士,并用围栏将其包围。这座巨大的孵化器在平面 OxyOxy 上呈一个具有 nn 个顶点的多边形。

很自然地,DravDe 无法坐视不管,他决心摧毁鸡帝国。当然,他将首先从这座孵化器下手。

DravDe 严格地位于孵化器区域之外的点 A(xa, ya)A(x_a,\,y_a) 处,并希望进入孵化器内部,消灭所有在那里工作的鸡。但这绝非易事!问题在于:最近 DravDe 去玩轮滑,结果摔断了两条腿。他将乘坐喷气式飞机 LEVAP-41 抵达孵化器区域。

LEVAP-41 的飞行速度为 V(xv, yv, zv)V(x_v,\,y_v,\,z_v)。DravDe 可在点 AA 登机,飞行一段时间后跳伞。由于 DravDe 体重过大,他将以垂直向下的速度 FdownF_{\text{down}} 自由下落;但在自由下落过程中的任意一点,他均可打开降落伞;此后,他将随风飘落,其下落速度变为风速 U(xu, yu, zu)U(x_u,\,y_u,\,z_u),直至着陆。

不幸的是,DravDe 并不擅长数学。您能否帮助这位可怜的世界救世主,找出一种跳伞方案,使其最终降落在孵化器的区域内?若满足条件的方案不唯一,DravDe 希望选择飞机飞行时间最短的方案;若仍存在多个方案,则他希望选择自由下落(即开伞前)时间最短的方案。

输入格式

The first line contains the number n (3 ≤ n ≤ 104) — the amount of vertices of the fence. Then there follow n lines containing the coordinates of these vertices (two integer numbers x__i, y__i) in clockwise or counter-clockwise order. It's guaranteed, that the fence does not contain self-intersections.

The following four lines contain coordinates of point A(x__a, y__a), speeds V(x__v, y__v, z__v), F__down and speed U(x__u, y__u, z__u). All the input numbers are integer. All the coordinates don't exceed 104 in absolute value. It's guaranteed, that z__v > 0 and F__down, z__u < 0, and point A is strictly outside the incubator's territory.

第一行包含一个整数 $ n (( 3 \leq n \leq 10^4 $)——围栏的顶点数量。接下来有 $ n $ 行,每行包含一个顶点的坐标(两个整数 $ x_i,\ y_i $),按顺时针或逆时针顺序给出。保证围栏不自交。

随后四行分别给出点 $ A(x_a,\ y_a) $ 的坐标、速度向量 $ V(x_v,\ y_v,\ z_v) $、下拉力 $ F_{\text{down}} $ 以及速度向量 $ U(x_u,\ y_u,\ z_u) $。所有输入数据均为整数,且所有坐标的绝对值均不超过 $ 10^4 $。保证 $ z_v > 0 ,, F_{\text{down}},\ z_u < 0 $,且点 $ A $ 严格位于孵化箱区域之外。

输出格式

In the first line output two numbers _t_1, _t_2 such, that if DravDe air drops at time _t_1 (counting from the beginning of the flight), he lands on the incubator's territory (landing on the border is regarder as landing on the territory). If DravDe doesn't open his parachute, the second number should be equal to the duration of DravDe's falling down. If it's impossible for DravDe to get to the incubator's territory, output -1 -1. If the answer is not unique, output the answer with the minimum _t_1. If the answers are still multiple, output the answer with the minimum _t_2. Your answer must have an absolute or relative error less than 10 - 6.

第一行输出两个数 t1t_1 和 t2t_2,满足:若 DravDe 在时刻 t1t_1(从飞行开始计时)进行空投,则他将降落在孵化器的领地内(降落在边界上视为降落在领地内)。若 DravDe 不打开降落伞,则第二个数应等于 DravDe 下落的总时长。若 DravDe 不可能到达孵化器的领地,则输出 -1 -1。若答案不唯一,则输出其中 t1t_1 最小的解;若仍存在多个解,则输出其中 t2t_2 最小的解。你的答案必须满足绝对误差或相对误差小于 10−610^{-6}。

输入输出样例

  • 输入#1

    4
    0 0
    1 0
    1 1
    0 1
    0 -1
    1 0 1
    -1
    0 1 -1

    输出#1

    1.00000000 0.00000000
  • 输入#2

    4
    0 0
    0 1
    1 1
    1 0
    0 -1
    -1 -1 1
    -1
    0 1 -1

    输出#2

    -1.00000000 -1.00000000
  • 输入#3

    4
    0 0
    1 0
    1 1
    0 1
    0 -1
    1 1 1
    -1
    1 1 -1

    输出#3

    0.50000000 0.00000000

输入解题思路,AI测评打分。不知道怎么写?

首页