Pagini recente » Cod sursa (job #1531873) | Cod sursa (job #1480455) | Cod sursa (job #959937) | Cod sursa (job #1816200) | Cod sursa (job #946958)
Cod sursa(job #946958)
#include<fstream>
#include<cmath>
#include<iomanip>
#include<algorithm>
using namespace std ;
#define maxn 120001
#define eps 0.000000000001
#define pi 3.14159265358979323846
#define inf 2000000000.0
ifstream fin("rubarba.in");
ofstream fout("rubarba.out");
int n ;
pair<double, double> v[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 ;
for(int i = 1; i <= n; ++i )
{
fin >> 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 ;
double XA = X * C - Y * S ;
double YA = X * S + Y * C ;
fout << setprecision(2) << fixed ;
fout << XA << " " << YA << "\n" ;
maxX = max( maxX, XA ) ;
minX = min( minX, XA ) ;
maxY = max( maxY, YA ) ;
minY = min( minY, YA ) ;
}
fout<<endl;
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 ) ] ;
long double panta = ( (long double)v[p2].second - v[p1].second ) / ((long double) v[p2].first - v[p1].first ) ;
//fout<<panta<<endl;
long double unghi = - atan2( v[p1].second - v[p2].second, v[p1].first - v[p2].first ) ;
fout << v[p1].first << " " << v[p1].second << " " << v[p2].first << " " << v[p2].second << endl ;
fout << unghi << endl ;
rotire( unghi ) ;
}
}
void afisare()
{
fout << setprecision(2) << fixed ;
for(int i = 1; i <= nr; ++i )
fout << v[ stiva[i] ].first << " " << v[ stiva[i] ].second << "\n" ;
fout << A ;
}
int main()
{
citire() ;
infasuratoare() ;
rezolvare() ;
afisare() ;
return 0 ;
}