F. Paris by Night

Codeforces

IDCF10246F

Time15000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Hence, she will proceed as follows. She chooses two monuments, that we will call the #cf_span(class=[tex-font-style-underline], body=[boundary monuments]), and asks the balloon pilot to go between these monuments. From there, she takes two $180^compose$ pictures: each picture shows one side of Paris, both sides being delimited by the two boundary monuments. Each picture receives a grade, which is the sum of the grades of the monuments that it shows, including the boundary monuments on both pictures. Finally, if the pictures have grades A and B, the goal of Morgane is to minimize the difference between A and B (in absolute value). The visibility from the balloon is such that all monuments can be seen in either of the two photographs. You must assist Morgane in choosing appropriate boundary monuments. In order to do this, you are given a list of the monuments. For every monument visited by Morgane, this list contains a line which indicates the Cartesian coordinates of the monument location, along with the monument's grade. You should give the minimal possible difference, among all pairs of pictures that Morgane may take, between the grades of the two pictures. *Important Note* Morgane was so precise at locating every monument that no three monuments are on a same straight line. The input comprises several lines, each consisting of integers separated with single spaces: *Limits* The output should consist of a single line, whose content is an integer, the minimal difference (in absolute value) between the grades of a pair of photographs that Morgane may take. ## Input The input comprises several lines, each consisting of integers separated with single spaces: the first line contains the number N of monuments; each of the N next lines contains three integers associated with each monument: the X coordinate, the Y coordinate and the grade G of the monument represented on that line. *Limits* $2 <= N <= 4000$; $0 <= X, " "Y <= 1000000000$ and $1 <= G <= 1000000000$. ## Output The output should consist of a single line, whose content is an integer, the minimal difference (in absolute value) between the grades of a pair of photographs that Morgane may take. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of monuments. For each monument $ i \in \{1, \dots, n\} $, let $ (x_i, y_i) \in \mathbb{R}^2 $ be its Cartesian coordinates and $ g_i \in \mathbb{Z} $ be its grade. Let $ \mathcal{P} = \{ (i, j) \mid 1 \leq i < j \leq n \} $ be the set of all unordered pairs of distinct monuments, representing potential boundary monument pairs. For each pair $ (i, j) \in \mathcal{P} $, the line through monuments $ i $ and $ j $ divides the plane into two half-planes. Let $ S_{ij}^+ $ and $ S_{ij}^- $ be the sets of monument indices lying strictly in each open half-plane (excluding $ i $ and $ j $). Define the grade of each photograph as: - $ A_{ij} = g_i + g_j + \sum_{k \in S_{ij}^+} g_k $ - $ B_{ij} = g_i + g_j + \sum_{k \in S_{ij}^-} g_k $ **Constraints** 1. No three monuments are collinear. 2. All monument coordinates and grades are given as integers. **Objective** Compute: $$ \min_{(i,j) \in \mathcal{P}} \left| A_{ij} - B_{ij} \right| $$

API Response (JSON)

{
  "problem": {
    "name": "F. Paris by Night",
    "description": {
      "content": "Hence, she will proceed as follows. She chooses two monuments, that we will call the #cf_span(class=[tex-font-style-underline], body=[boundary monuments]), and asks the balloon pilot to go between the",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 15000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10246F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Hence, she will proceed as follows. She chooses two monuments, that we will call the #cf_span(class=[tex-font-style-underline], body=[boundary monuments]), and asks the balloon pilot to go between the...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of monuments.  \nFor each monument $ i \\in \\{1, \\dots, n\\} $, let $ (x_i, y_i) \\in \\mathbb{R}^2 $ be its Cartesian coordinates and $ g_i \\in \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments