D. Large Triangle

Codeforces

IDCF1019D

Time3000ms

Memory256MB

Difficulty—

binary searchgeometrysortings

English · Original

Chinese · Translation

Formal · Original

> > There is a strange peculiarity: if you connect the cities of Rostov, Taganrog and Shakhty, peculiarly, you get a triangle> — «Unbelievable But True»Students from many different parts of Russia and abroad come to Summer Informatics School. You marked the hometowns of the SIS participants on a map. Now you decided to prepare an interesting infographic based on this map. The first thing you chose to do is to find three cities on this map, such that they form a triangle with area $S$. ## Input The first line of input contains two integers $n$ and $S$ ($3 \le n \le 2000$, $1 \le S \le 2 \cdot 10^{18}$) — the number of cities on the map and the area of the triangle to be found. The next $n$ lines contain descriptions of the cities, one per line. Each city is described by its integer coordinates $x_i$, $y_i$ ($-10^9 \le x_i, y_i \le 10^9$). It is guaranteed that all cities are located at distinct points. It is also guaranteed that no three cities lie on the same line. ## Output If the solution doesn't exist — print «_No_». Otherwise, print «_Yes_», followed by three pairs of coordinates $(x, y)$ — the locations of the three cities, which form the triangle of area $S$. [samples]

来自俄罗斯各地及海外的学生来到夏季信息学学校。你已在地图上标记了SIS参与者的家乡。现在你打算基于这张地图制作一个有趣的信息图。你首先决定找出地图上的三个城市，使它们构成一个面积为 $S$ 的三角形。输入的第一行包含两个整数 $n$ 和 $S$（$3 lt.eq n lt.eq 2000$，$1 lt.eq S lt.eq 2 dot.op 10^(18)$）—— 分别表示地图上的城市数量和目标三角形的面积。接下来的 $n$ 行每行描述一个城市，包含其整数坐标 $x_i$, $y_i$（$-10^9 lt.eq x_i, y_i lt.eq 10^9$）。保证所有城市位于不同的点，且任意三个城市都不共线。如果无解，请输出 «_No_»。否则，输出 «_Yes_»，随后跟三对坐标 $(x, y)$ —— 构成面积为 $S$ 的三角形的三个城市的位置。 ## Input 输入的第一行包含两个整数 $n$ 和 $S$（$3 lt.eq n lt.eq 2000$，$1 lt.eq S lt.eq 2 dot.op 10^(18)$）—— 分别表示地图上的城市数量和目标三角形的面积。接下来的 $n$ 行每行描述一个城市，包含其整数坐标 $x_i$, $y_i$（$-10^9 lt.eq x_i, y_i lt.eq 10^9$）。保证所有城市位于不同的点，且任意三个城市都不共线。 ## Output 如果无解，请输出 «_No_»。否则，输出 «_Yes_»，随后跟三对坐标 $(x, y)$ —— 构成面积为 $S$ 的三角形的三个城市的位置。 [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the number of cities. Let $ S \in \mathbb{Z}^+ $ be the target area. Let $ P = \{ (x_i, y_i) \mid i \in \{1, \dots, n\} \} $ be a set of $ n $ distinct points in $ \mathbb{R}^2 $, with no three collinear. **Constraints** 1. $ 3 \leq n \leq 2000 $ 2. $ 1 \leq S \leq 2 \cdot 10^{18} $ 3. $ -10^9 \leq x_i, y_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $ 4. All points in $ P $ are distinct. 5. No three points in $ P $ are collinear. **Objective** Find three distinct points $ A = (x_a, y_a), B = (x_b, y_b), C = (x_c, y_c) \in P $ such that the area of triangle $ \triangle ABC $ equals $ S $, where the area is given by: $$ \text{Area} = \frac{1}{2} \left| (x_b - x_a)(y_c - y_a) - (x_c - x_a)(y_b - y_a) \right| $$ If such a triple exists, output: ``` Yes x_a y_a x_b y_b x_c y_c ``` Otherwise, output: ``` No ```

Samples

Input #1

Output #1

No

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "D. Large Triangle",
    "description": {
      "content": "> > There is a strange peculiarity: if you connect the cities of Rostov, Taganrog and Shakhty, peculiarly, you get a triangle> — «Unbelievable But True»Students from many different parts of Russia and",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF1019D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "> > There is a strange peculiarity: if you connect the cities of Rostov, Taganrog and Shakhty, peculiarly, you get a triangle> — «Unbelievable But True»Students from many different parts of Russia and...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "来自俄罗斯各地及海外的学生来到夏季信息学学校。你已在地图上标记了SIS参与者的家乡。\n\n现在你打算基于这张地图制作一个有趣的信息图。你首先决定找出地图上的三个城市，使它们构成一个面积为 $S$ 的三角形。\n\n输入的第一行包含两个整数 $n$ 和 $S$（$3 lt.eq n lt.eq 2000$，$1 lt.eq S lt.eq 2 dot.op 10^(18)$）—— 分别表示地图上的城市数量...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of cities.  \nLet $ S \\in \\mathbb{Z}^+ $ be the target area.  \nLet $ P = \\{ (x_i, y_i) \\mid i \\in \\{1, \\dots, n\\} \\} $ be a set of $ n $ distinc...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments