codeforces Photo of The Sky

标签: photo of   the sky  思维

题目链接:http://codeforces.com/contest/1013/problem/C
题意:给你2*n 个整数,要求你把这2*n个数分为两组,一组为x坐标,一组为y坐标,每组n个数。任你选一种组合方式,让其组成n个点,使得包含所有xy坐标表示的点的矩形(边与坐标轴平行)的最小面积。输出最小面积
分析:对于此题,不要一头扎进怎么组合中,跳出来进行思考。
要求能包含所有点的最小矩形面积,我们就必须确定矩形的长和宽的大小。我们可以把所有的坐标进行排序,对于矩形的边长,一种考虑方式是使所有的边的点靠的越进越好,所以就是
(a[n]-a[1])*(a[2*n]-a[n+1]) 另外一种情况是:最大和最小作为边,然后找其中间对应点差值最小的作为边。
从网上找到三张图,能够很形象的说明这个问题:

从小到大进行排列:
这里写图片描述

情况1:
这里写图片描述

情况2:
这里写图片描述


#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6+10;

long long a[maxn];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n*2;i++){
        scanf("%lld",&a[i]);
    }
    sort(a,a+n*2);
    long long ans=(a[n-1]-a[0])*(a[n*2-1]-a[n]);
    for(int i=1;i<n;i++){
        ans=min(ans,(a[i+n-1]-a[i])*(a[n*2-1]-a[0]));
    }
    printf("%lld\n",ans);
    return 0;
}
原文链接:加载失败,请重新获取