题解：P13581 [NWRRC 2023] Axis-Aligned Area

· · 题解

题意与分析

给出 4 根木棍，求它们所能围成的最大的封闭图形的面积。

当输入为 2 2 4 7 时，参考下面这张图片。
此时，可以围成的最大的图形面积是 8。

思路

还是观察刚才这张图片，显然还有其它围法。但之所以样例的答案是围成矩形，就说明矩形在所有围法中是最佳的。

现在，我们已经确定要围成矩形。

矩形面积公式

大家都知道矩形面积公式是 a\times b，其中 a,b 是长和宽。但是我们应该怎么得到矩形的长和宽呢？

假设有两条边 x,y 是矩形上的对边，那么显然 x=y。
现在我们有一组对边 a_i,a_j，不一定满足 a_i=a_j，那么我们就需要截断其中一条线端，使它们的长度能够满足 a_i=a_j。

总结出规律：x=y=\min\{a_i,a_j\}。

要求我们将 a_1,a_2,a_3,a_4 分成两组，分别求组内的最小值，再求乘积（面积）。题目求面积的最大值。

最优分组策略

已知 a_1\le a_2\le a_3\le a_4。

\because a_3\ge a_2,\ a_1>0\\ \therefore a_1a_3\ge a_1a_2\\ \therefore S_3\ge S_1=S_2

综上，将 a_1,a_2 分成一组，a_3,a_4 分成一组是最优分组策略。
所以求出其围成的矩形的面积，公式如下。

S=\min\{a_1,a_2\}\times\min\{a_3,a_4\}=a_1\times a_3

代码

#include<bits/stdc++.h>
using namespace std;
int a[5];
int main(){
    for(int i=1; i<=4; i++)
        cin >> a[i];
    cout << a[1]*a[3];
}