Cod sursa(job #2765826)

Utilizator BossBobsterRobert Alexandru Costin BossBobster Data 30 iulie 2021 04:13:07
Problema Rubarba Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.18 kb
#include <iostream>
#include <string.h>
#include <random>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iomanip>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <complex>
#include <valarray>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, string> pis;
typedef pair<string, string> pss;
typedef pair<int, char> pic;
typedef pair<pii, int> piii;
typedef pair<double, double> pdd;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ull, ull> pull;
typedef complex<double> cd;
//#define max(n, m) ((n>m)?n:m)
//#define min(n, m) ((n<m)?n:m)
#define f first
#define s second
#define input() ios_base::sync_with_stdio(0);cin.tie(0);

ifstream fin("rubarbe.in");
ofstream fout("rubarbe.out");

struct pt
{
    ld x, y;
    bool operator<(const pt& p1) const
    {
        if(p1.x == x) return y < p1.y;
        return x < p1.x;
    }
};
int cp(pt p1, pt p2)
{
    return p1.x * p2.y - p1.y * p2.x;
}
int ccw(pt p1, pt p2, pt p3)
{
    pt p4 = {p2.x - p1.x, p2.y - p1.y};
    pt p5 = {p3.x - p1.x, p3.y - p1.y};
    if(cp(p4, p5) > 0) return 1; // ccw
    return -1; // cw
}
int n;
ld mxX, mxY, mnX, mnY, sn, cs;
vector<pt> nums;
vector<pt> upper;
vector<pt> lower;
vector<ld> angles;
ld ans(ld ang)
{
    mxX = mxY = -2000000000000000000; mnX = mnY = 2000000000000000000;
    sn = sin(ang), cs = cos(ang);
    for(int i = 0; i < n; i ++)
        mxX = max(mxX, nums[i].x*cs - nums[i].y*sn), mnX = min(mnX, nums[i].x*cs - nums[i].y*sn), mxY = max(mxY, nums[i].x*sn + nums[i].y*cs), mnY = min(mnY, nums[i].x*sn + nums[i].y*cs);
    ld ret = (mxX-mnX) * (mxY-mnY);
    return ret;
}
ld bs(ld l, ld r)
{
    ld mid = (l+r)/2;
    if(abs(l - r) < 0.0000000003) return l;
    if(ans(mid) > ans(mid + 0.0000000001))
        return bs(mid+0.0000000001, r);
    return bs(l, mid);
}
int main()
{
    fin >> n;
    nums.resize(n);
    for(int i = 0; i < n; i ++)
        fin >> nums[i].x >> nums[i].y;
    sort(nums.begin(), nums.end());
    for(int i = 0; i < n; i ++)
    {
        while(upper.size() >= 2 && ccw(upper[upper.size() - 2], upper.back(), nums[i]) == 1)
            upper.pop_back();
        upper.push_back(nums[i]);
    }
    for(int i = n-1; i >= 0; i --)
    {
        while(lower.size() >= 2 && ccw(lower[lower.size() - 2], lower.back(), nums[i]) == 1)
            lower.pop_back();
        lower.push_back(nums[i]);
    }
    for(int i = 0; i < upper.size()-1; i ++)
        angles.push_back(atan((ld)(upper[i+1].y - upper[i].y))/(ld)(upper[i+1].x - upper[i].x));
    for(int i = 0; i < lower.size()-1; i ++)
        angles.push_back(atan((ld)(lower[i+1].y - lower[i].y))/(ld)(lower[i+1].x - lower[i].x));
    for(int i = 0; i < angles.size(); i ++)
        if(angles[i] < 0)
            angles[i] += M_PI;
    sort(angles.begin(), angles.end());
    fout << fixed << setprecision(2) << ans(bs(0, M_PI)) << "\n";
    return 1;
}