Cod sursa(job #1235441)

Utilizator matei_cChristescu Matei matei_c Data 29 septembrie 2014 19:37:23
Problema Rubarba Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.3 kb
#include<fstream>
#include<cmath>
#include<iomanip>
#include<limits>
#include<algorithm>
using namespace std ;

#define maxn 120001
#define eps 0.000000000001
#define pi 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679
#define inf 1000000000000000.0

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

int n ;

//double inf = numeric_limits<double>::max() ;

pair<double, double> v[maxn], nou[maxn] ;

double A = inf ;

bool sel[maxn] ;

int stiva[maxn], nr ;

int pas = 1 ;

int verifica(int x)
{
    if( x == n )
        pas = -pas ;

    return pas ;
}

void citire()
{
    fin >> n ;

    if( n == 1 || n == 2 )
    {
        fout << "0.00" ;
        return ;
    }

    for(int i = 1; i <= n; ++i )
    {
        fin >> v[i].first >> v[i].second ;
        ++v[i].first ;
        ++v[i].second ;
    }
}

double produs( pair<double, double> X, pair<double, double> A, pair<double, double> B )
{
    return ( A.first - X.first ) * ( B.second - X.second ) - ( B.first - X.first ) * ( A.second - X.second ) ;
}

void infasuratoare()
{
    sort( v + 1, v + n + 1 ) ;

    stiva[1] = 1 ;
    stiva[2] = 2 ;
    nr = 2 ;
    sel[2] = true ;

   for(int i = 3; i > 0; i += verifica(i) )
    {
        if( sel[i] )
            continue ;

        while( nr >= 2 && produs( v[ stiva[ nr - 1 ] ], v[ stiva[nr] ], v[i] ) <= 0 )
            sel[ stiva[ nr-- ] ] = false ;

        stiva[++nr] = i ;
        sel[i] = true ;
    }

    --nr ;
}

void rotire(double unghi)
{
    double S = sin( unghi ) ;
    double C = cos( unghi ) ;

    double maxX = -inf ;
    double minX = inf ;

    double maxY = -inf ;
    double minY = inf ;

    for(int i = 1; i <= nr; ++i )
    {
        double X = v[ stiva[i] ].first ;
        double Y = v[ stiva[i] ].second ;

        nou[i].first = X * C - Y * S ;
        nou[i].second = X * S + Y * C ;

        maxX = max( maxX, nou[i].first ) ;
        minX = min( minX, nou[i].first ) ;

        maxY = max( maxY, nou[i].second ) ;
        minY = min( minY, nou[i].second ) ;
    }

    double Aact = ( maxX - minX ) * ( maxY - minY ) ;
    A = min( A, Aact ) ;
}

void rezolvare()
{
    for(int i = 1; i <= nr; ++i )
    {
        int p1 = stiva[i] ;
        int p2 = stiva[ ( i + 1 ) % nr ] ;

        double panta, unghi ;
        bool ok = false ;

        if( fabs( v[p2].first - v[p1].first ) < eps )
        {
            unghi = pi / 2 ;
            ok = true ;
        }

        if( ok == false )
        {
            panta = ( v[p2].second - v[p1].second ) / ( v[p2].first - v[p1].first ) ;

            if( panta < 0 )
                unghi = pi / 2 + atan( -panta ) ;
            else
                unghi = pi / 2 - atan( panta ) ;

        }

        rotire( unghi ) ;
    }
}

void afisare()
{
    /*
    fout << --nr << "\n" ;

    fout << setprecision(6) << fixed ;

    for(int i = 1; i <= nr; ++i )
        fout << v[ stiva[i] ].first << " " << v[ stiva[i] ].second << "\n" ;

    */
    fout << setprecision(2) << fixed ;

    fout << A ;
}

int main()
{
    citire() ;

    if( n == 1 || n == 2 )
        return 0 ;

    infasuratoare() ;

    rezolvare() ;

    afisare() ;

    return 0 ;
}