P3142 题解

· · 题解

题目传送门

思路

没有任何技巧可言，只卖三只牛，单纯暴力。想要求出最终围栏围起来的面积，只需要计算 (maxx-minx)(maxy-miny) 的值即可。

首先，我们先用 X_i 排序，求得最大的 3 个点和最小的 3 个点。同样的方法给 Y_i 排序，求得最大的 3 个点和最小的 3 个点。我们要暴力的答案中必定包含这 12 个点（当然有重复的点要去重）。

接下来就是暴力的核心，用 dfs 每一次选择 3 个点，然后最后计算它的面积，取最小值即可。（如果这个不会，建议先做这道题）