Cod sursa(job #2632012)

Utilizator Senth30Denis-Florin Cringanu Senth30 Data 1 iulie 2020 21:01:13
Problema Rubarba Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <bits/stdc++.h>
#define MAX 131072
#define MOD 10007
#define INF 2100000000
#define pi 1.5707963267948966192313216916398
#define eps 1e-17

using namespace std;
const int NMAX = 100100;

FILE *IN, *OUT;

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

struct obj{
    int x, y;
}v[NMAX];

int N;

int poz, sign;
char f[MAX];

inline void Read(int &nr){
    sign = 0;
    nr = 0;
    while(f[poz] < '0' || f[poz] > '9'){
        if(f[poz] == '-') sign = 1;
        ++poz;
        if(poz == MAX)
            fread(f, MAX, 1, IN), poz = 0;
    }
    while(f[poz] >= '0' && f[poz] <= '9'){
        nr = 10 * nr + f[poz++] - '0';
        if(poz == MAX)
            fread(f, MAX, 1, IN), poz = 0;
    }
    if(sign) nr =- nr;
}

void read(){
    fin >> N;
    for(int i = 1; i <= N; i++)
        fin >> v[i].x >> v[i].y;
}

long double solve(long double angle){
    long double xMax = -INF, xMin = INF, yMax = -INF, yMin = INF;
    long double s = sin(angle), c = cos(angle);
    for(int i = 1; i <= N; i++){
        long double x = v[i].x * c - v[i].y * s;
        long double y = v[i].x * s + v[i].y * c;
        xMax = max(xMax, x);
        xMin = min(xMin, x);
        yMax = max(yMax, y);
        yMin = min(yMin, y);
    }
    return (xMax - xMin) * (yMax - yMin);
}

int main(){

    read();
    long double st = 0, dr = pi, mid;
    while(dr - st > eps){
        mid = st + (dr - st) / 2;
        if(solve(mid) > solve(mid + eps))
            st = mid;
        else dr = mid;
    }
    fout << fixed << setprecision(5) << solve(mid);

    return 0;
}