Now we need to build a fortress. The fortress is a rectangular area, with the upper left corner in. Now it is required to eliminate all monsters and find the minimum area of the fortress, that is, minimize
There is a a grid with n n rows and m m columns, in which there are k k monsters. The i i th monster lives in (x_i, y_i) (x i ,y i ) (the x_i x i th row of the y_i y i th column). Now we need to build a fortress. The fortress is a rectangular area, with the upper left corner in (r_1, c_1) (r 1 ,c 1 ) and the lower right corner in (r_2, c_2) (r 2 ,c 2 ). All the rows between r_1 r 1 and r_2 r 2 and the columns between c_1 c 1 and c_2 c 2 belong to the fortress. A valid fortress requires 1le r_1 le r_2le n, 1 le c_1 le c_2 le m 1≤r 1 ≤r 2 ≤n,1≤c 1 ≤c 2 ≤m After building the fortress, all monsters i i satisfy r_1 le x_i le r_2 r 1 ≤x i ≤r 2 or c_1le y_i le c_2 c 1 ≤y i ≤c 2 will be eliminated (i.e. the attack area of the fortress is a cross area) Now it is required to eliminate all monsters and find the minimum area of the fortress, that is, minimize (r_2-r_1+1)*(c_2-c_1+1) (r 2 −r 1 +1)∗(c 2 −c 1 +1)
