J. Empty Circle

Codeforces

IDCF10074J

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You are given a set of n points S = {p1, p2, ..., pn} on the plane. A triple (pi, pj, pk) is called #cf_span(class=[tex-font-style-underline], body=[good]) if no point in S is strictly inside the circumference of these three points. If it is possible, find a good triple! The first line contains an integer n, the number of the points (3 ≤ n ≤ 106). The i-th of the next n lines contains two integer numbers xi and yi, the coordinates of pi ( - 104 ≤ xi, yi ≤ 104). No two given points will be equal. If a good triple exists, output "_Yes_" in the first line. In the next line output three space-separated integers, the numbers of the three points as they appeared in the input. If no good triple exists, output "_No_" in a single line. ## Input The first line contains an integer n, the number of the points (3 ≤ n ≤ 106). The i-th of the next n lines contains two integer numbers xi and yi, the coordinates of pi ( - 104 ≤ xi, yi ≤ 104). No two given points will be equal. ## Output If a good triple exists, output "_Yes_" in the first line. In the next line output three space-separated integers, the numbers of the three points as they appeared in the input.If no good triple exists, output "_No_" in a single line. [samples]

**Definitions** Let $ S = \{p_1, p_2, \dots, p_n\} \subset \mathbb{R}^2 $ be a set of $ n \geq 3 $ distinct points in the plane. For a triple $ (p_i, p_j, p_k) \in S^3 $ with $ i < j < k $, let $ C(p_i, p_j, p_k) $ denote the unique circle passing through $ p_i, p_j, p_k $ (if non-collinear). **Constraint** A triple $ (p_i, p_j, p_k) $ is *good* if: - $ p_i, p_j, p_k $ are not collinear, and - No point $ p_\ell \in S \setminus \{p_i, p_j, p_k\} $ lies strictly inside $ C(p_i, p_j, p_k) $. **Objective** Determine whether there exists a good triple in $ S $. If yes, output "Yes" followed by the 1-based indices of any such triple; otherwise, output "No".

API Response (JSON)

{
  "problem": {
    "name": "J. Empty Circle",
    "description": {
      "content": "You are given a set of n points S = {p1, p2, ..., pn} on the plane. A triple (pi, pj, pk) is called #cf_span(class=[tex-font-style-underline], body=[good]) if no point in S is strictly inside the circ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10074J"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a set of n points S = {p1, p2, ..., pn} on the plane. A triple (pi, pj, pk) is called #cf_span(class=[tex-font-style-underline], body=[good]) if no point in S is strictly inside the circ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ S = \\{p_1, p_2, \\dots, p_n\\} \\subset \\mathbb{R}^2 $ be a set of $ n \\geq 3 $ distinct points in the plane.  \nFor a triple $ (p_i, p_j, p_k) \\in S^3 $ with $ i < j < k $, let $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments