Pagini recente » Cod sursa (job #264235) | Cod sursa (job #347055) | Cod sursa (job #3002275) | Cod sursa (job #2505897) | Cod sursa (job #938363)
Cod sursa(job #938363)
#include<cstdio>
#include<iostream>
#include<iomanip>
#include<algorithm>
using namespace std ;
#define maxn 120001
#define eps 0.000000000001
int n ;
pair<double, double> v[maxn] ;
bool sel[maxn] ;
int stiva[maxn], nr ;
int pas = 1 ;
int verifica(int x)
{
if( x == n )
pas = -pas ;
return pas ;
}
void citire()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
cin >> n ;
for(int i = 1; i <= n; ++i )
cin >> 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 = 1; i > 0; i += verifica(i) )
{
if( sel[i] )
continue ;
while( nr >= 2 && produs( v[ stiva[ nr - 1 ] ], v[ stiva[nr] ], v[i] ) < eps )
sel[ stiva[ nr-- ] ] = false ;
stiva[++nr] = i ;
sel[i] = true ;
}
}
void afisare()
{
cout << nr - 1 << "\n" ;
cout << setprecision(6) << fixed ;
for(int i = 1; i < nr; ++i )
cout << v[ stiva[i] ].first << " " << v[ stiva[i] ].second << "\n" ;
}
int main()
{
citire() ;
infasuratoare() ;
afisare() ;
return 0 ;
}