H. Split Game

Codeforces

IDCF10123H

Time1000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

Consider the following game about splitting a simple polygon with N vertices on a plane. The purpose of this game is using a straight line which passes through the origin to split the given simple polygon into as many non-zero area regions as possible. Please finish the game with the best result possible. The input consists of N + 1 lines. The first line contains an integer N. The i-th of the following N lines consists of two integers xi and yi indicating the vertices of the given polygon in counter-clockwise order. Also, the actual lower bound on N is 3. Output one integer: the maximum number of non-zero area regions into which the given polygon can be split by a single line passing through the origin. ## Input The input consists of N + 1 lines. The first line contains an integer N. The i-th of the following N lines consists of two integers xi and yi indicating the vertices of the given polygon in counter-clockwise order. Also, the actual lower bound on N is 3. 1 ≤ N ≤ 105 1 ≤ xi, yi ≤ 109 if i ≠ j, then (xi, yi) ≠ (xj, yj) the vertices are given in counter-clockwise order the polygon is simple: its sides have no common points except the vertices ## Output Output one integer: the maximum number of non-zero area regions into which the given polygon can be split by a single line passing through the origin. [samples]

**Definitions** Let $ N \in \mathbb{Z} $, $ N \geq 3 $, be the number of vertices of a simple polygon. Let $ P = (v_1, v_2, \dots, v_N) $, where $ v_i = (x_i, y_i) \in \mathbb{R}^2 $, be the sequence of vertices given in counter-clockwise order. Let $ \mathcal{L} $ be the set of all lines in $ \mathbb{R}^2 $ passing through the origin $ (0,0) $. **Constraints** - The polygon $ P $ is simple (non-self-intersecting). - The origin $ (0,0) $ may lie inside, on the boundary, or outside the polygon. **Objective** Find the maximum number of connected components of positive area into which $ P $ can be partitioned by a single line $ \ell \in \mathcal{L} $. That is, compute: $$ \max_{\ell \in \mathcal{L}} \left| \left\{ C \subseteq P \cap \mathbb{R}^2 \mid C \text{ is a connected component of } P \setminus \ell \text{ and } \text{area}(C) > 0 \right\} \right| $$

API Response (JSON)

{
  "problem": {
    "name": "H. Split Game",
    "description": {
      "content": "Consider the following game about splitting a simple polygon with N vertices on a plane. The purpose of this game is using a straight line which passes through the origin to split the given simple pol",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10123H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Consider the following game about splitting a simple polygon with N vertices on a plane. The purpose of this game is using a straight line which passes through the origin to split the given simple pol...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z} $, $ N \\geq 3 $, be the number of vertices of a simple polygon.  \nLet $ P = (v_1, v_2, \\dots, v_N) $, where $ v_i = (x_i, y_i) \\in \\mathbb{R}^2 $, be the seque...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments