Pagini recente » Cod sursa (job #375981) | Cod sursa (job #2124927) | Cod sursa (job #2235640) | Cod sursa (job #1680504) | Cod sursa (job #1235441)
#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 ;
}