{"problem":{"name":"C. Fifa and Fafa","description":{"content":"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 t","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF935C"},"statements":[{"statement_type":"Markdown","content":"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.\n\nThe 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.\n\n## Input\n\nThe 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).\n\n## Output\n\nPrint 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.\n\nYour 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.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Fifa 和 Fafa 共享一套公寓。Fifa 热爱电子游戏，想要下载一款新的足球游戏。不幸的是，Fafa 大量使用互联网，消耗了流量配额。Fifa 可以通过他的 Wi-Fi 接入点访问互联网。该接入点的覆盖范围是以其位置为中心、半径为 #cf_span[r] 米的圆形区域（该范围可由 Fifa 自行选择）。Fifa 必须将接入点放置在公寓内部，公寓呈圆形，半径为 #cf_span[R]。Fifa 希望在不使 Fafa 或公寓外任何人获得互联网访问权限的前提下，最小化公寓内未被接入点覆盖的区域。\n\n世界被表示为一个无限的二维平面。公寓的中心位于 #cf_span[(x1, y1)]，半径为 #cf_span[R]，Fafa 的笔记本电脑位于 #cf_span[(x2, y2)]，不一定在公寓内部。请找出 Fifa 为接入点选择的位置和半径，以最小化未覆盖的面积。\n\n输入的一行包含 5 个用空格分隔的整数 #cf_span[R, x1, y1, x2, y2]（#cf_span[1 ≤ R ≤ 10^5]，#cf_span[|x1|, |y1|, |x2|, |y2| ≤ 10^5]）。\n\n请输出三个用空格分隔的数字 #cf_span[xap, yap, r]，其中 #cf_span[(xap, yap)] 是 Fifa 选择的接入点位置，#cf_span[r] 是其覆盖范围的半径。\n\n你的答案将被视为正确，当且仅当所输出的半径与最优值的绝对或相对误差不超过 #cf_span[10^{-6}]，并且你可以将输出的半径在不超过 #cf_span[10^{-6}]（绝对或相对）的范围内调整，使得所有公寓外部的点以及 Fafa 笔记本电脑的位置都位于接入点覆盖圆的外部。\n\n## Input\n\n输入的一行包含 5 个用空格分隔的整数 #cf_span[R, x1, y1, x2, y2]（#cf_span[1 ≤ R ≤ 10^5]，#cf_span[|x1|, |y1|, |x2|, |y2| ≤ 10^5]）。\n\n## Output\n\n请输出三个用空格分隔的数字 #cf_span[xap, yap, r]，其中 #cf_span[(xap, yap)] 是 Fifa 选择的接入点位置，#cf_span[r] 是其覆盖范围的半径。你的答案将被视为正确，当且仅当所输出的半径与最优值的绝对或相对误差不超过 #cf_span[10^{-6}]，并且你可以将输出的半径在不超过 #cf_span[10^{-6}]（绝对或相对）的范围内调整，使得所有公寓外部的点以及 Fafa 笔记本电脑的位置都位于接入点覆盖圆的外部。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ C_{\\text{flat}} = \\{ (x, y) \\in \\mathbb{R}^2 \\mid (x - x_1)^2 + (y - y_1)^2 \\leq R^2 \\} $ be the flat, a closed disk centered at $ (x_1, y_1) $ with radius $ R $.  \nLet $ P = (x_2, y_2) $ be the position of Fafa’s laptop.  \nLet $ C_{\\text{ap}} = \\{ (x, y) \\in \\mathbb{R}^2 \\mid (x - x_{\\text{ap}})^2 + (y - y_{\\text{ap}})^2 \\leq r^2 \\} $ be the access point’s coverage disk, with center $ (x_{\\text{ap}}, y_{\\text{ap}}) $ and radius $ r $.\n\n**Constraints**  \n1. $ C_{\\text{ap}} \\subseteq C_{\\text{flat}} $  \n2. $ P \\notin C_{\\text{ap}} $\n\n**Objective**  \nMinimize the area of $ C_{\\text{flat}} \\setminus C_{\\text{ap}} $, i.e., maximize the area of $ C_{\\text{ap}} $ subject to the above constraints.\n\n**Solution**  \nLet $ d = \\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} $ be the distance from the flat center to Fafa’s laptop.  \n- If $ d \\geq R $, then $ P \\notin C_{\\text{flat}} $, so set $ (x_{\\text{ap}}, y_{\\text{ap}}, r) = (x_1, y_1, R) $.  \n- If $ d < R $, then the optimal $ C_{\\text{ap}} $ is the largest disk inside $ C_{\\text{flat}} $ that does not contain $ P $. This is achieved by placing the access point on the line segment from $ (x_1, y_1) $ to $ (x_2, y_2) $, at distance $ R - r $ from $ (x_1, y_1) $, such that $ r = \\frac{R + d}{2} $ and the center is at:  \n  $$\n  (x_{\\text{ap}}, y_{\\text{ap}}) = \\left( x_1 + \\frac{R - r}{d}(x_2 - x_1),\\ y_1 + \\frac{R - r}{d}(y_2 - y_1) \\right)\n  $$  \n  Substituting $ r = \\frac{R + d}{2} $, we get $ R - r = \\frac{R - d}{2} $, so:  \n  $$\n  (x_{\\text{ap}}, y_{\\text{ap}}) = \\left( x_1 + \\frac{R - d}{2d}(x_2 - x_1),\\ y_1 + \\frac{R - d}{2d}(y_2 - y_1) \\right)\n  $$  \n  and $ r = \\frac{R + d}{2} $.\n\n**Output**  \nPrint $ x_{\\text{ap}}, y_{\\text{ap}}, r $ as defined above.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF935C","tags":["geometry"],"sample_group":[["5 3 3 1 1","3.7677669529663684 3.7677669529663684 3.914213562373095"],["10 5 5 5 15","5.0 5.0 10.0"]],"created_at":"2026-03-03 11:00:39"}}