C. Light Festival

Codeforces

IDCF10275C

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

After losing control of his time machine, Akash finds himself in the middle of late 19th century America, just as Thomas Edison is creating a festival to show off his light bulbs to the masses. Edison is planning on setting up the main showcase at a particular location, represented by a 2D point. To ensure his festival is a success, Edison wants every single person in town to see his festival by appropriately setting the brightness of the lights. If he makes the lights brighter, more people are able to see the lights, but it costs him more money to do so. Given the locations of all the people in town as 2D points, Edison wants to find the farthest person from the main showcase so that he can set the brightness accordingly. Can Akash find the distance of the farthest person from Edison's showcase? The first line will consist of a single integer $n$ ($1 <= n <= 10^5$) representing the number of people in town. The next line consists of two integers $a, b$ ($-10^9 <= a, b <= 10^9$) indicating the location of Edison's showcase. The next $n$ lines consist of two integers $x, y$ ($-10^9 <= x, y <= 10^9$) indicating that there is a person at coordinate $(x, y)$ Output the distance of the farthest person from Edison's main showcase. Your answer will be judged as correct if it is within $10^(-6)$ of the true answer. ## Input The first line will consist of a single integer $n$ ($1 <= n <= 10^5$) representing the number of people in town. The next line consists of two integers $a, b$ ($-10^9 <= a, b <= 10^9$) indicating the location of Edison's showcase. The next $n$ lines consist of two integers $x, y$ ($-10^9 <= x, y <= 10^9$) indicating that there is a person at coordinate $(x, y)$ ## Output Output the distance of the farthest person from Edison's main showcase. Your answer will be judged as correct if it is within $10^(-6)$ of the true answer. [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the number of people. Let $ P = (a, b) \in \mathbb{R}^2 $ be the location of Edison's showcase. Let $ Q_i = (x_i, y_i) \in \mathbb{R}^2 $ for $ i \in \{1, \dots, n\} $ be the locations of the people. **Constraints** 1. $ 1 \leq n \leq 10^5 $ 2. $ -10^9 \leq a, b \leq 10^9 $ 3. $ -10^9 \leq x_i, y_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $ **Objective** Compute the maximum Euclidean distance from $ P $ to any $ Q_i $: $$ \max_{1 \leq i \leq n} \sqrt{(x_i - a)^2 + (y_i - b)^2} $$

API Response (JSON)

{
  "problem": {
    "name": "C. Light Festival",
    "description": {
      "content": "After losing control of his time machine, Akash finds himself in the middle of late 19th century America, just as Thomas Edison is creating a festival to show off his light bulbs to the masses. Edison",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10275C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "After losing control of his time machine, Akash finds himself in the middle of late 19th century America, just as Thomas Edison is creating a festival to show off his light bulbs to the masses. Edison...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of people.  \nLet $ P = (a, b) \\in \\mathbb{R}^2 $ be the location of Edison's showcase.  \nLet $ Q_i = (x_i, y_i) \\in \\mathbb{R}^2 $ for $ i \\in ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments