200. Rubber Bands

Codeforces

IDCF10269200

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You have placed $n$ pins on a bulletin board, and a rubber band. You want to place the rubber band around a certain subset of the pins, such that there aren't any pins inside of the rubber band that aren't touching the rubber band. In other words, the rubber band must touch all of the points inside of it. Figure out the largest number of pins that you can choose, and still satisfy the condition described above. The first line of input contains a single positive integer $n$, less than or equal to 7: the number of pins. The next $n$ lines each contain two space-separated integers $x$ and $y$: the x and y coordinates of each pin, respectively. Output a single positive integer $k$: the size of the largest subset of pins that you can wrap the rubber band around, such that the rubber band is touching all points inside of the rubber band. ## Input The first line of input contains a single positive integer $n$, less than or equal to 7: the number of pins.The next $n$ lines each contain two space-separated integers $x$ and $y$: the x and y coordinates of each pin, respectively. ## Output Output a single positive integer $k$: the size of the largest subset of pins that you can wrap the rubber band around, such that the rubber band is touching all points inside of the rubber band. [samples]

**Definitions** Let $ P = \{p_1, p_2, \dots, p_n\} \subset \mathbb{R}^2 $ be a set of $ n \leq 7 $ points in the plane, where each $ p_i = (x_i, y_i) $. **Objective** Find the maximum size $ k $ of a subset $ S \subseteq P $ such that all points in $ P \setminus S $ lie strictly outside the convex hull of $ S $, i.e., $$ \text{conv}(S) \cap P = S $$ Equivalently, $ S $ is a subset of $ P $ whose convex hull contains no other points of $ P $ in its interior or on its boundary except those in $ S $.

API Response (JSON)

{
  "problem": {
    "name": "200. Rubber Bands",
    "description": {
      "content": "You have placed $n$ pins on a bulletin board, and a rubber band. You want to place the rubber band around a certain subset of the pins, such that there aren't any pins inside of the rubber band that a",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10269200"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You have placed $n$ pins on a bulletin board, and a rubber band. You want to place the rubber band around a certain subset of the pins, such that there aren't any pins inside of the rubber band that a...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ P = \\{p_1, p_2, \\dots, p_n\\} \\subset \\mathbb{R}^2 $ be a set of $ n \\leq 7 $ points in the plane, where each $ p_i = (x_i, y_i) $.\n\n**Objective**  \nFind the maximum size $ k $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments