编程题:农田缩减
农夫约翰的 N 头奶牛分布在其二维农场的不同位置。
约翰想用一个长方形的围栏把所有的奶牛围起来,围栏的边需要平行于 x 轴和 y 轴。
在能够包含所有奶牛的情况下(处于围栏边界的奶牛也算包含在内),约翰希望围栏围起的面积尽可能小。
不幸的是,由于上个季度的牛奶产量很低,约翰的预算十分紧张。
因此,他希望建立一个更小的围栏,甚至为了实现这一目标,他愿意卖掉农场中的一头奶牛。
请帮助约翰计算,卖掉牛群中的一头奶牛以后,他可以用围栏围起来的最小面积(为剩下的奶牛建造尽可能小的围栏)。
对于这个问题,请将奶牛视为点,将围栏视为四个线段的集合。
注意,答案可以是零,例如,所有剩余的奶牛最终都站在同一条垂直或水平线上。
### 输入格式:
第一行包含整数 N(3≤N≤50000 ,)。
接下来 N 行,每行包含两个整数 x,y(1≤x,y≤40000),表示一头牛所在的位置坐标为 (x,y)。
### 输出格式:
输出卖掉牛群中的一头奶牛以后,约翰可以用围栏围起来的最小面积。
### 输入样例:
in
4
2 4
1 1
5 2
17 25
### 输出样例:
out
12
答案:若无答案欢迎评论
约翰想用一个长方形的围栏把所有的奶牛围起来,围栏的边需要平行于 x 轴和 y 轴。
在能够包含所有奶牛的情况下(处于围栏边界的奶牛也算包含在内),约翰希望围栏围起的面积尽可能小。
不幸的是,由于上个季度的牛奶产量很低,约翰的预算十分紧张。
因此,他希望建立一个更小的围栏,甚至为了实现这一目标,他愿意卖掉农场中的一头奶牛。
请帮助约翰计算,卖掉牛群中的一头奶牛以后,他可以用围栏围起来的最小面积(为剩下的奶牛建造尽可能小的围栏)。
对于这个问题,请将奶牛视为点,将围栏视为四个线段的集合。
注意,答案可以是零,例如,所有剩余的奶牛最终都站在同一条垂直或水平线上。
### 输入格式:
第一行包含整数 N(3≤N≤50000 ,)。
接下来 N 行,每行包含两个整数 x,y(1≤x,y≤40000),表示一头牛所在的位置坐标为 (x,y)。
### 输出格式:
输出卖掉牛群中的一头奶牛以后,约翰可以用围栏围起来的最小面积。
### 输入样例:
in
4
2 4
1 1
5 2
17 25
### 输出样例:
out
12
答案:若无答案欢迎评论