B. Rectangles

Codeforces

IDCF10088B

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

You have N rectangles, all of their sides are either parallel to X axis or to Y axis, and you want to cover them all using one big rectangle. what is the minimum area of the big rectangle you need in order to cover all the rectangles. The first line contains number of test cases T Each test case consists of an integer N (1 ≤ N ≤ 1000), followed by N lines, each line describes a rectangle with four pairs of integers representing the X coordinate and Y coordinate of the vertices. - 1000 ≤ Xcoordinate, Ycoordinate ≤ 1000 For each test case print one integer which is the size of the rectangular cover. ## Input The first line contains number of test cases T Each test case consists of an integer N (1 ≤ N ≤ 1000), followed by N lines, each line describes a rectangle with four pairs of integers representing the X coordinate and Y coordinate of the vertices. - 1000 ≤ Xcoordinate, Ycoordinate ≤ 1000 ## Output For each test case print one integer which is the size of the rectangular cover. [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case $ k \in \{1, \dots, T\} $: - Let $ N_k \in \mathbb{Z} $ denote the size of the array. - Let $ A_k = (a_{k,1}, a_{k,2}, \dots, a_{k,N_k}) $ be a sequence of non-negative integers. **Constraints** 1. $ 1 \le T \le 20 $ 2. For each $ k \in \{1, \dots, T\} $: - $ 1 \le N_k \le 10^5 $ - $ 0 \le a_{k,i} \le 10^9 $ for all $ i \in \{1, \dots, N_k\} $ **Objective** Find the minimum number of adjacent merge operations required to transform $ A_k $ into a *mirror array* (i.e., $ b_i = b_{m+1-i} $ for all $ i $, where $ m $ is the final length), where a merge operation replaces two adjacent elements $ x, y $ with $ x + y $.

API Response (JSON)

{
  "problem": {
    "name": "B. Rectangles",
    "description": {
      "content": "You have N rectangles, all of their sides are either parallel to X axis or to Y axis, and you want to cover them all using one big rectangle.  what is the minimum area of the big rectangle you need i",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10088B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You have N rectangles, all of their sides are either parallel to X axis or to Y axis, and you want to cover them all using one big rectangle. \n\nwhat is the minimum area of the big rectangle you need i...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ N_k \\in \\mathbb{Z} $ denote the size of the array.  \n- Let $ A_k = (a_...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments