天空的照片

时间: 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;

}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。