C. Two Seals

Codeforces
IDCF837C
Time1000ms
Memory256MB
Difficulty
brute forceimplementation
English · Original
Chinese · Translation
Formal · Original
One very important person has a piece of paper in the form of a rectangle _a_ × _b_. Also, he has _n_ seals. Each seal leaves an impression on the paper in the form of a rectangle of the size _x__i_ × _y__i_. Each impression must be parallel to the sides of the piece of paper (but seal can be rotated by 90 degrees). A very important person wants to choose two different seals and put them two impressions. Each of the selected seals puts exactly one impression. Impressions should not overlap (but they can touch sides), and the total area occupied by them should be the largest possible. What is the largest area that can be occupied by two seals? ## Input The first line contains three integer numbers _n_, _a_ and _b_ (1 ≤ _n_, _a_, _b_ ≤ 100). Each of the next _n_ lines contain two numbers _x__i_, _y__i_ (1 ≤ _x__i_, _y__i_ ≤ 100). ## Output Print the largest total area that can be occupied by two seals. If you can not select two seals, print _0_. [samples] ## Note In the first example you can rotate the second seal by 90 degrees. Then put impression of it right under the impression of the first seal. This will occupy all the piece of paper. In the second example you can't choose the last seal because it doesn't fit. By choosing the first and the third seals you occupy the largest area. In the third example there is no such pair of seals that they both can fit on a piece of paper.
一位非常重要的人拥有一张矩形纸张,尺寸为 $a × b$。 此外,他有 $n$ 枚印章。每枚印章在纸上留下一个尺寸为 $x_i × y_i$ 的矩形印记。每个印记必须与纸张的边平行(但印章可以旋转 90 度)。 这位重要的人希望选择两枚不同的印章,并各盖一个印记。每个选中的印章恰好盖一个印记。印记之间不能重叠(但可以边对边接触),且它们占据的总面积应尽可能大。求两枚印章能占据的最大总面积。 第一行包含三个整数 $n$、$a$ 和 $b$($1 ≤ n, a, b ≤ 100$)。 接下来的 $n$ 行,每行包含两个数 $x_i$、$y_i$($1 ≤ x_i, y_i ≤ 100$)。 请输出两枚印章能占据的最大总面积。如果无法选择两枚印章,请输出 _0_。 在第一个例子中,你可以将第二枚印章旋转 90 度,然后将其印记放在第一枚印章印记的正下方。这样将完全占满整张纸。 在第二个例子中,你不能选择最后一枚印章,因为它无法放入。通过选择第一枚和第三枚印章,你可以占据最大的面积。 在第三个例子中,不存在任何一对印章能同时放在纸张上。 ## Input 第一行包含三个整数 $n$、$a$ 和 $b$($1 ≤ n, a, b ≤ 100$)。每行接下来的 $n$ 行包含两个数 $x_i$、$y_i$($1 ≤ x_i, y_i ≤ 100$)。 ## Output 请输出两枚印章能占据的最大总面积。如果无法选择两枚印章,请输出 _0_。 [samples] ## Note 在第一个例子中,你可以将第二枚印章旋转 90 度,然后将其印记放在第一枚印章印记的正下方。这样将完全占满整张纸。在第二个例子中,你不能选择最后一枚印章,因为它无法放入。通过选择第一枚和第三枚印章,你可以占据最大的面积。在第三个例子中,不存在任何一对印章能同时放在纸张上。
**Definitions** Let $ n, a, b \in \mathbb{Z}^+ $ denote the number of seals and dimensions of the paper. Let $ S = \{ (x_i, y_i) \mid i \in \{1, \dots, n\} \} $ be the set of seal dimensions, where each seal can be placed as $ (x_i, y_i) $ or $ (y_i, x_i) $ (i.e., rotated 90 degrees). **Constraints** 1. $ 1 \leq n, a, b \leq 100 $ 2. For each seal $ i $, $ 1 \leq x_i, y_i \leq 100 $ 3. Each seal impression must fit entirely within the $ a \times b $ rectangle: $$ \min(x_i, y_i) \leq \max(a, b) \quad \text{and} \quad \max(x_i, y_i) \leq \max(a, b) $$ and at least one orientation satisfies: $$ (x_i \leq a \land y_i \leq b) \quad \text{or} \quad (x_i \leq b \land y_i \leq a) $$ **Objective** Find the maximum total area $ A = A_1 + A_2 $, where: - $ A_1 = x_{i} \cdot y_{i} $, $ A_2 = x_{j} \cdot y_{j} $ for two distinct seals $ i \ne j $, - Each seal is placed in one of its two orientations, - The two rectangular impressions fit non-overlappingly within the $ a \times b $ paper. That is, maximize: $$ \max_{\substack{i,j \in \{1,\dots,n\} \\ i \ne j}} \left\{ x_i y_i + x_j y_j \ \middle| \ \begin{array}{c} \exists \text{ orientations } o_i, o_j \text{ such that } \\ o_i \text{ fits in } a \times b, \\ o_j \text{ fits in } a \times b, \\ o_i \text{ and } o_j \text{ can be placed non-overlappingly in } a \times b \end{array} \right\} $$ If no such pair exists, output $ 0 $.
Samples
Input #1
2 2 2
1 2
2 1
Output #1
4
Input #2
4 10 9
2 3
1 1
5 10
9 11
Output #2
56
Input #3
3 10 10
6 6
7 7
20 5
Output #3
0
API Response (JSON)
{
  "problem": {
    "name": "C. Two Seals",
    "description": {
      "content": "One very important person has a piece of paper in the form of a rectangle _a_ × _b_. Also, he has _n_ seals. Each seal leaves an impression on the paper in the form of a rectangle of the size _x__i_ ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF837C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "One very important person has a piece of paper in the form of a rectangle _a_ × _b_.\n\nAlso, he has _n_ seals. Each seal leaves an impression on the paper in the form of a rectangle of the size _x__i_ ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "一位非常重要的人拥有一张矩形纸张,尺寸为 $a × b$。\n\n此外,他有 $n$ 枚印章。每枚印章在纸上留下一个尺寸为 $x_i × y_i$ 的矩形印记。每个印记必须与纸张的边平行(但印章可以旋转 90 度)。\n\n这位重要的人希望选择两枚不同的印章,并各盖一个印记。每个选中的印章恰好盖一个印记。印记之间不能重叠(但可以边对边接触),且它们占据的总面积应尽可能大。求两枚印章能占据的最大总面积。\n\n...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, a, b \\in \\mathbb{Z}^+ $ denote the number of seals and dimensions of the paper.  \nLet $ S = \\{ (x_i, y_i) \\mid i \\in \\{1, \\dots, n\\} \\} $ be the set of seal dimensions, wher...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments