本文主要是介绍Codeforces Round #500 (Div. 2) [based on EJOI] C. Photo of The Sky (思维)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://codeforces.com/contest/1013/problem/C
题意：给你2N个数字,你可以任意排列，让你排成N个坐标，问你包含这N个坐标的矩形的面积最小值。
思路：我们先将这N个数排列，前一半较小的我们称为集合a，后一半较大的我们称为集合b，要想求矩形面积我们只要知道对角坐标（x1，y1），（x2，y2）就行了，面积就是(x2−x1)∗(y2−y1)，我们分两种情况讨论：
- x1和y1分别在a，b两个集合，x2，y2也在a，b两个集合，这时要想矩形最小而且包含所有的点，很容易就想到一个点是a集合的最小值和b集合的最小值（组成一个点），另一个点就是a集合的最大值，和b集合的最大值（组成一个点），此时矩形的面积就是：ans = (a[n]-a[1]) * (a[n*2]-a[n+1])；
- x1，y1在a集合，x2，y2在b集合，因为要包含所有的点我们先确定矩形的长（N个数中最大值与最小值的差）k = a[n*2] - a[1]，要想矩形最小所以要宽最小，要包含所有的点我们就要对应取点（a集合的第一个数和b集合的第一个数对应，以此类推），我们枚举对应的点寻找差值最小的即可。
记得开long long。
#include<bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
using namespace std;
const int maxn = 1e6+10;
ll a[maxn];
int main()
{int n;scanf("%d",&n);for(int i = 1; i <= n*2; i++)scanf("%lld",&a[i]);sort(a+1,a+1+n*2);ll ans = (a[n]-a[1]) * (a[n*2]-a[n+1]);ll k = a[n*2] - a[1];for(int i = 2; i <= n; i++)ans = min(ans, (a[i+n-1] - a[i]) * k);printf("%lld\n",ans);return 0;
}
这篇关于Codeforces Round #500 (Div. 2) [based on EJOI] C. Photo of The Sky (思维)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
