THE QUESTION
Text from the official booklet. Refer to the PDF for original mathematical notation, formatting, and linked input files. Printed samples and inputs are reproduced as published.
At WonderLand Theme Park, there are N attractions (3 ≤ N ≤ 50, 000), each located at a distinct point on a 2D map. The map is a coordinate grid. Each attraction is at a point ( x, y), where x and y are positive integers between 1 and 1 , 000, 000, 000. The park management wants to build fences around the attractions to mark safety zones. Single Enclosure: If they build one rectangular fence: • The fence must have sides parallel to the x- and y-axes. • It must contain every attraction (attractions on the boundary are allowed). • Among all such rectangles, they will choose the smallest possible one (with mini- mum area) that contains all attractions. Two Enclosures: However, the park wants to save money on maintenance by reducing the total fenced area. They consider using two separate rectangular enclosures instead of one: • Each enclosure must also have sides parallel to the axes. • Together, the two enclosures must still contain all attractions (every attraction must lie inside at least one of the two rectangles; being on the boundary is allowed). • The two rectangles are not allowed to overlap, not even at the boundary (they must be completely disjoint). • Rectangles with zero area are allowed (for example, if width = 0 or height = 0). Goal: Compute how much total area the park can save by using two enclosures instead of one. Input Format: • First line: N – the number of attractions. • Next N lines: Each contains two integers x y, the coordinates of an attraction. All attraction positions are distinct, and 1 ≤ x, y≤ 1, 000, 000, 000. Output Format: Output a single integer: The maximum area saved by using two enclosures instead of one. Sample Input: 6 4 2 8 10 1 1 9 12 14 7 2 3 Sample Output: 107 Question Input: 100 10 12 14 18 18 20 22 25 26 30 30 35 34 40 38 45 42 50 46 55 50 60 54 65 58 70 62 75 66 80 70 85 74 90 78 95 82 100 86 105 12 14 16 22 20 28 24 34 28 42 32 48 36 52 40 58 44 63 48 68 52 73 56 78 60 83 64 88 68 92 72 96 76 102 80 108 84 114 88 120 15 130 20 135 25 140 30 145 35 150 40 155 45 160 50 165 55 170 60 175 65 180 70 185 75 190 80 195 85 200 18 150 22 144 26 138 30 132 34 126 38 120 42 116 46 112 50 108 54 104 58 100 62 96 66 92 70 88 74 84 78 80 82 76 86 72 90 68 94 64 98 60 102 56 106 52 110 48 114 44 118 40 122 36 126 32 130 28 134 24 138 20 142 16 146 12 150 18 154 24 158 30 162 36 166 42 170 48 174 54 178 60 182 66 186 72 190 78 194 84 198 90 199 95 200 100