CF935C.Fifa and Fafa
普及/提高-
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Fifa and Fafa are sharing a flat. Fifa loves video games and wants to download a new soccer game. Unfortunately, Fafa heavily uses the internet which consumes the quota. Fifa can access the internet through his Wi-Fi access point. This access point can be accessed within a range of r meters (this range can be chosen by Fifa) from its position. Fifa must put the access point inside the flat which has a circular shape of radius R. Fifa wants to minimize the area that is not covered by the access point inside the flat without letting Fafa or anyone outside the flat to get access to the internet.
The world is represented as an infinite 2D plane. The flat is centered at (_x_1, _y_1) and has radius R and Fafa's laptop is located at (_x_2, _y_2), not necessarily inside the flat. Find the position and the radius chosen by Fifa for his access point which minimizes the uncovered area.
Fifa 和 Fafa 合住一套公寓。Fifa 热爱电子游戏,想要下载一款新的足球游戏。不幸的是,Fafa 大量使用互联网,消耗了大量流量配额。Fifa 可以通过自己的 Wi-Fi 接入点接入互联网。该接入点的信号覆盖范围为 r 米(该范围由 Fifa 自行选择),即从其位置起半径为 r 的圆形区域。Fifa 必须将该接入点放置在公寓内部,而该公寓呈圆形,圆心位于 (_x_1, _y_1),半径为 R。Fifa 希望在不使 Fafa 或公寓外的任何人能够接入互联网的前提下,最小化公寓内未被接入点覆盖的面积。
整个世界被建模为一个无限大的二维平面。公寓是以 (_x_1, _y_1) 为圆心、半径为 R 的圆形区域;Fafa 的笔记本电脑位于 (_x_2, _y_2),该位置不一定在公寓内部。请确定 Fifa 所选接入点的位置及其半径 r,使得公寓内未被覆盖的面积最小。
输入格式
The single line of the input contains 5 space-separated integers R, _x_1, _y_1, _x_2, _y_2 (1 ≤ R ≤ 105, |_x_1|, |_y_1|, |_x_2|, |_y_2| ≤ 105).
输入仅包含一行,其中有 5 个以空格分隔的整数 R、x1、y1、x2、y2(满足 1 ≤ R ≤ 105,∣x1∣, ∣y1∣, ∣x2∣, ∣y2∣ ≤ 105)。
输出格式
Print three space-separated numbers x__ap, y__ap, r where (x__ap, y__ap) is the position which Fifa chose for the access point and r is the radius of its range.
Your answer will be considered correct if the radius does not differ from optimal more than 10 - 6 absolutely or relatively, and also the radius you printed can be changed by no more than 10 - 6 (absolutely or relatively) in such a way that all points outside the flat and Fafa's laptop position are outside circle of the access point range.
输出三个以空格分隔的数 xap, yap, r,其中 (xap, yap) 是 Fifa 为接入点所选定的位置,r 是其覆盖范围的半径。
若满足以下条件,则你的答案视为正确:
- 所输出的半径 r 与最优半径的绝对或相对误差均不超过 10−6;
- 且所输出的半径 r 可在绝对或相对误差不超过 10−6 的范围内进行微调,使得所有位于平面外部的点以及 Fafa 的笔记本电脑位置均严格位于该接入点覆盖圆的外部。
输入输出样例
输入#1
5 3 3 1 1
输出#1
3.7677669529663684 3.7677669529663684 3.914213562373095
输入#2
10 5 5 5 15
输出#2
5.0 5.0 10.0
输入解题思路,AI测评打分。不知道怎么写?