C. Photo of The Sky

题目链接

Codeforces Round #500 (Div. 2) [based on EJOI]--C. Photo of The Sky

题解

中档题。题意大概是给定一组坐标的乱序排列,求出可能的最小矩形面积以覆盖这些坐标。
首先将坐标排序,连续n个数作为x坐标,其余的均作为y坐标,其中x,y坐标的最大最小值即是矩形的边界。求出其中的最小值即可。

代码

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const long long INF = 1ll << 60;
int n;
long long a[200005];
long long ans = INF;
int main() {
    cin >> n;
    for (int i = 1; i <= 2 * n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + 2 * n + 1);
    ans = (a[2 * n] - a[n + 1])*(a[n] - a[1]);
    for (int i = 2; i <= n; i++) {
        ans = min(ans, (a[2 * n] - a[1])*(a[i + n - 1] - a[i]));
    }
    cout << ans;
}

标签: implementation, math

添加新评论