天空的照片
时间： 1ms 内存：128M
描述：
给出2*n个数，任意n个作为横坐标（可自己自由选择），其余n个作为纵坐标，两两任意组合，形成n个点，使得能够包含这n个点的矩形的面积最小。
输入：
n (1≤n≤100000)，第二行包含2*n个整数a1,a2,a3,a4….an(1<=ai<=1e9)。
输出：
输出矩形的最小面积。
示例输入：
4
4 1 3 2 3 2 1 3
示例输出：
1提示：
参考答案（内存最优[3584]）：
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
long long val[2 * N];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= 2 * n; i++)
cin >> val[i];
sort(val + 1, val + 1 + 2 * n);
long long mn = (val[n] - val[1]) * (val[2 * n] - val[n + 1]);
for (int i = 2; i <= n + 1; i++)
{
long long tmp = (val[1] - val[2 * n])*(val[i] - val[i + n - 1]);
mn = min(mn, tmp);
}
cout << mn << endl;
}
参考答案（时间最优[3]）：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
long long a[2*N];
int main()
{
int n;
cin>>n;
int i,j,k;
for(i=1;i<=2*n;i++)
{
cin>>a[i];
}
sort(a+1,a+1+2*n);
long long mn=(a[1]-a[n])*(a[n+1]-a[2*n]);
for(i=2;i<=n+1;i++)
{
mn=min(mn,(a[1]-a[2*n])*(a[i]-a[i+n-1]));
}
cout<<mn<<endl;
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。