C. Rectangles

Codeforces

IDCF10230C

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Sancho is a weird kid, he really likes rectangles. You are in charge of babysitting him and you want to keep Sancho distracted. You decided to give him a gridded sheet of paper with many dots in it, so that Sancho can draw a lot of rectangles by connecting those dots. You don't want him to get overwhelmed with too many rectangles, so you want to know what is the number of distinct rectangles that can be formed such that each of the rectangle's vertexes is a dot, there are no dots inside or on the edges of the rectangle besides the ones on its vertexes and all sides are parallel to the axis of the grid. The first line of the input contains one integer $N$ $(1 <= N <= 2000)$, indicating how many dots there are total in the sheet. $N$ lines will follow. The $i$th line will contain two numbers $x$ $(0 <= x <= 10^9)$ and $y$ $(0 <= y <= 10^9)$. The pair $(x, y)$ represents the coordinate of the $i$th dot on the sheet. No two dots will be in the same position. Output the number of distinct of rectangles that can be formed such that each vertex of the rectangle is a dot, there are no dots inside or on the edges of the rectangle besides the ones on its vertexes and each rectangle is parallel to the axis of the grid. ## Input The first line of the input contains one integer $N$ $(1 <= N <= 2000)$, indicating how many dots there are total in the sheet. $N$ lines will follow. The $i$th line will contain two numbers $x$ $(0 <= x <= 10^9)$ and $y$ $(0 <= y <= 10^9)$. The pair $(x, y)$ represents the coordinate of the $i$th dot on the sheet. No two dots will be in the same position. ## Output Output the number of distinct of rectangles that can be formed such that each vertex of the rectangle is a dot, there are no dots inside or on the edges of the rectangle besides the ones on its vertexes and each rectangle is parallel to the axis of the grid. [samples]

**Definitions** Let $ \mathbf{P} = (x_0, y_0) $, $ \mathbf{Q} = (x_1, y_1) $ be the initial and target positions in $ \mathbb{R}^2 $. Let $ \mathbf{g} = (0, -9.80665) \, \text{m/s}^2 $ be the gravitational acceleration. Let $ v_{\text{max}} \geq 0 $ be the maximum initial speed magnitude. Let $ \mathbf{v}_0 = (v_x, v_y) \in \mathbb{R}^2 $ be the initial velocity vector. Let $ t > 0 $ be the time of flight. **Constraints** 1. $ \mathbf{B}(t) = \mathbf{P} + \mathbf{v}_0 t + \frac{1}{2} \mathbf{g} t^2 = \mathbf{Q} $ 2. $ \|\mathbf{v}_0\|^2 = v_x^2 + v_y^2 \leq v_{\text{max}}^2 $ 3. $ t > 0 $ **Objective** Find $ v_x, v_y, t $ such that the above constraints are satisfied.

API Response (JSON)

{
  "problem": {
    "name": "C. Rectangles",
    "description": {
      "content": "Sancho is a weird kid, he really likes rectangles. You are in charge of babysitting him and you want to keep Sancho distracted. You decided to give him a gridded sheet of paper with many dots in it, s",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10230C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Sancho is a weird kid, he really likes rectangles. You are in charge of babysitting him and you want to keep Sancho distracted. You decided to give him a gridded sheet of paper with many dots in it, s...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ \\mathbf{P} = (x_0, y_0) $, $ \\mathbf{Q} = (x_1, y_1) $ be the initial and target positions in $ \\mathbb{R}^2 $.  \nLet $ \\mathbf{g} = (0, -9.80665) \\, \\text{m/s}^2 $ be the grav...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments