1826. 农田缩减
摘要
Title: 1826. 农田缩减
Tag: 模拟
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
1826. 农田缩减
-
题意
农夫约翰的 N 头奶牛分布在其二维农场的不同位置。
约翰想用一个长方形的围栏把所有的奶牛围起来，围栏的边需要平行于 x 轴和 y 轴。
在能够包含所有奶牛的情况下（处于围栏边界的奶牛也算包含在内），约翰希望围栏围起的面积尽可能小。
不幸的是，由于上个季度的牛奶产量很低，约翰的预算十分紧张。
因此，他希望建立一个更小的围栏，甚至为了实现这一目标，他愿意卖掉农场中的一头奶牛。
请帮助约翰计算，卖掉牛群中的一头奶牛以后，他可以用围栏围起来的最小面积（为剩下的奶牛建造尽可能小的围栏）。
对于这个问题，请将奶牛视为点，将围栏视为四个线段的集合。
注意，答案可以是零，例如，所有剩余的奶牛最终都站在同一条垂直或水平线上。 -
思路
可以发现面积都是由最外层的点决定的，与去除里面的点无关，那么就分情况讨论即可，看是否最外层的点被去除了，如果去除了就挑次外面的
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32'''
Author: NEFU AB-IN
Date: 2022-01-27 20:57:53
FilePath: \ACM\Acwing\1826.py
LastEditTime: 2022-01-27 22:26:47
'''
A = []
INF = int(4e9)
X = []
Y = []
if __name__ == "__main__":
n = int(input())
maxn = 0
index = 0
for i in range(n):
x, y = map(int, input().split())
A.append((x, y))
X.append(x)
Y.append(y)
X.sort()
Y.sort()
res = INF
for i in range(n):
x1 = X[1] if A[i][0] == X[0] else X[0]
x2 = X[n - 2] if A[i][0] == X[n - 1] else X[n - 1]
y1 = Y[1] if A[i][1] == Y[0] else Y[0]
y2 = Y[n - 2] if A[i][1] == Y[n - 1] else Y[n - 1]
res = min(res, (x2 - x1) * (y2 - y1))
print(res)