G. Visible Black Areas

Codeforces

IDCF962G

Time1000ms

Memory256MB

Difficulty—

data structuresdsugeometrytrees

English · Original

Chinese · Translation

Formal · Original

Petya has a polygon consisting of $n$ vertices. All sides of the Petya's polygon are parallel to the coordinate axes, and each two adjacent sides of the Petya's polygon are perpendicular. It is guaranteed that the polygon is simple, that is, it doesn't have self-intersections and self-touches. All internal area of the polygon (borders are not included) was painted in black color by Petya. Also, Petya has a rectangular window, defined by its coordinates, through which he looks at the polygon. A rectangular window can not be moved. The sides of the rectangular window are parallel to the coordinate axes. <center>![image](https://espresso.codeforces.com/f1e813469b662d85fddcd0e754608f215d2f511b.png) Blue color represents the border of a polygon, red color is the Petya's window. The answer in this case is 2.</center>Determine the number of black connected areas of Petya's polygon, which can be seen through the rectangular window. ## Input The first line contain four integers $x_1, y_1, x_2, y_2$ ($x_1 < x_2$, $y_2 < y_1$) — the coordinates of top-left and bottom-right corners of the rectangular window. The second line contains a single integer $n$ ($4 \le n \le 15\,000$) — the number of vertices in Petya's polygon. Each of the following $n$ lines contains two integers — the coordinates of vertices of the Petya's polygon in counterclockwise order. Guaranteed, that the given polygon satisfies the conditions described in the statement. All coordinates of the rectangular window and all coordinates of the vertices of the polygon are non-negative and do not exceed $15\,000$. ## Output Print the number of black connected areas of Petya's polygon, which can be seen through the rectangular window. [samples] ## Note The example corresponds to the picture above.

Petya 有一个由 $n$ 个顶点组成的多边形。Petya 的多边形的所有边均平行于坐标轴，且每两条相邻边互相垂直。保证该多边形是简单的，即不存在自相交或自接触。Petya 将多边形的所有内部区域（不包括边界）涂成了黑色。此外，Petya 有一个矩形窗口，由其坐标定义，他通过该窗口观察多边形。矩形窗口不可移动，其边平行于坐标轴。请确定通过矩形窗口可以看到的 Petya 多边形中多少个黑色连通区域。第一行包含四个整数 $x_1, y_1, x_2, y_2$（$x_1 < x_2$，$y_2 < y_1$）——矩形窗口的左上角和右下角坐标。第二行包含一个整数 $n$（$4 lt.eq n lt.eq 15 thin 000$）——Petya 多边形的顶点数。接下来的 $n$ 行每行包含两个整数，表示按逆时针顺序给出的 Petya 多边形的顶点坐标。保证给出的多边形满足题目所述条件。矩形窗口和多边形所有顶点的坐标均为非负数，且不超过 $15 thin 000$。请输出可以通过矩形窗口看到的 Petya 多边形中黑色连通区域的数量。该示例对应于上图。 ## Input 第一行包含四个整数 $x_1, y_1, x_2, y_2$（$x_1 < x_2$，$y_2 < y_1$）——矩形窗口的左上角和右下角坐标。第二行包含一个整数 $n$（$4 lt.eq n lt.eq 15 thin 000$）——Petya 多边形的顶点数。接下来的 $n$ 行每行包含两个整数，表示按逆时针顺序给出的 Petya 多边形的顶点坐标。保证给出的多边形满足题目所述条件。矩形窗口和多边形所有顶点的坐标均为非负数，且不超过 $15 thin 000$。 ## Output 请输出可以通过矩形窗口看到的 Petya 多边形中黑色连通区域的数量。 [samples] ## Note 该示例对应于上图。

**Definitions** Let $ R = [x_1, x_2] \times [y_2, y_1] \subset \mathbb{R}^2 $ be the rectangular window, with $ x_1 < x_2 $, $ y_2 < y_1 $. Let $ P \subset \mathbb{R}^2 $ be a simple polygon with $ n $ vertices, given in counterclockwise order, such that: - All edges of $ P $ are axis-aligned (horizontal or vertical). - Consecutive edges are perpendicular (i.e., $ P $ is a rectilinear polygon). - The interior of $ P $ is colored black. Let $ \text{int}(P) $ denote the open interior of $ P $ (excluding boundary). Let $ C_1, C_2, \dots, C_m $ be the connected components of $ \text{int}(P) $. **Constraints** 1. $ 4 \le n \le 15{,}000 $ 2. All vertex coordinates and window coordinates are integers in $ [0, 15{,}000] $ 3. $ R $ is axis-aligned and fixed. **Objective** Compute the number of connected components $ C_i $ of $ \text{int}(P) $ such that $ C_i \cap R \neq \emptyset $. That is, compute: $$ \left| \left\{ C_i \mid C_i \text{ is a connected component of } \text{int}(P) \text{ and } C_i \cap R \neq \emptyset \right\} \right| $$

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "G. Visible Black Areas",
    "description": {
      "content": "Petya has a polygon consisting of $n$ vertices. All sides of the Petya's polygon are parallel to the coordinate axes, and each two adjacent sides of the Petya's polygon are perpendicular. It is guaran",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF962G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Petya has a polygon consisting of $n$ vertices. All sides of the Petya's polygon are parallel to the coordinate axes, and each two adjacent sides of the Petya's polygon are perpendicular. It is guaran...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Petya 有一个由 $n$ 个顶点组成的多边形。Petya 的多边形的所有边均平行于坐标轴，且每两条相邻边互相垂直。保证该多边形是简单的，即不存在自相交或自接触。Petya 将多边形的所有内部区域（不包括边界）涂成了黑色。\n\n此外，Petya 有一个矩形窗口，由其坐标定义，他通过该窗口观察多边形。矩形窗口不可移动，其边平行于坐标轴。\n\n请确定通过矩形窗口可以看到的 Petya 多边形中多少个黑色...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ R = [x_1, x_2] \\times [y_2, y_1] \\subset \\mathbb{R}^2 $ be the rectangular window, with $ x_1 < x_2 $, $ y_2 < y_1 $.  \nLet $ P \\subset \\mathbb{R}^2 $ be a simple polygon with ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments