2114D.md (2144B)
1 Source: https://codeforces.com/problemset/problem/2114/D 2 3 D. Come a Little Closer 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 The game field is a matrix of size $10^9 \times 10^9$, with a cell at the intersection of the $a$-th row and the $b$-th column denoted as ($a, b$). 22 23 There are $n$ monsters on the game field, with the $i$-th monster located in the cell ($x_i, y_i$), while the other cells are empty. No more than one monster can occupy a single cell. 24 25 You can move one monster to any cell on the field that is not occupied by another monster at most once . 26 27 After that, you must select one rectangle on the field; all monsters within the selected rectangle will be destroyed. You must pay $1$ coin for each cell in the selected rectangle. 28 29 Your task is to find the minimum number of coins required to destroy all the monsters. 30 31 Input 32 33 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 34 35 The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of monsters on the field. 36 37 The following $n$ lines contain two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le 10^9$) — the coordinates of the cell with the $i$-th monster. All pairs ($x_i, y_i$) are distinct. 38 39 It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$. 40 41 Output 42 43 For each test case, output a single integer — the minimum cost to destroy all $n$ monsters. 44 45 Example 46 47 Input 48 49 ``` 50 7 51 52 3 53 54 1 1 55 56 1 2 57 58 2 1 59 60 5 61 62 1 1 63 64 2 6 65 66 6 4 67 68 3 3 69 70 8 2 71 72 4 73 74 1 1 75 76 1 1000000000 77 78 1000000000 1 79 80 1000000000 1000000000 81 82 1 83 84 1 1 85 86 5 87 88 1 2 89 90 4 2 91 92 4 3 93 94 3 1 95 96 3 2 97 98 3 99 100 1 1 101 102 2 5 103 104 2 2 105 106 4 107 108 4 3 109 110 3 1 111 112 4 4 113 114 1 2 115 ``` 116 117 Output 118 119 ``` 120 3 121 32 122 1000000000000000000 123 1 124 6 125 4 126 8 127 ``` 128 129 Note 130 131 Below are examples of optimal moves, with the cells of the rectangle to be selected highlighted in green. 132 133  Required move for the first example.  Required move for the fifth example.