Pagini recente » Cod sursa (job #460094) | Cod sursa (job #1799506) | Cod sursa (job #2216879) | Cod sursa (job #1812751) | Cod sursa (job #1257244)
/*
* Code by Spiromanul
*/
#include <fstream>
#include <bitset>
#include <algorithm>
#include <iomanip>
#define EPS 1e-12
const char IN [ ] = "infasuratoare.in" ;
const char OUT [ ] = "infasuratoare.out" ;
const int MAX = 120014 ;
using namespace std;
ifstream fin ( IN ) ;
ofstream fout ( OUT ) ;
typedef pair < double , double > P ;
P puncte [ MAX ] ;
bitset < MAX > viz ;
int st [ MAX ] , varf ;
double determin ( const P &a , const P &b , const P &o )
{
return ( 1LL * o.first * a.second + 1LL * a.first * b.second + 1LL * b.first * o.second - 1LL * a.second * b.first - 1LL * b.second * o.first - 1LL * a.first * o.second ) ;
}
int main( )
{
int n ;
fin >> n ;
for ( int i = 1 ; i <= n ; ++ i )
fin >> puncte [ i ].first >> puncte [ i ].second ;
sort ( puncte + 1 , puncte + n + 1 ) ;
st [ 1 ] = 1 ;
st [ 2 ] = 2 ;
varf = 2 ;
viz [ 2 ] = 1 ;
int p = 1 ;
for ( int i = 1 ; i > 0 ; i += ( p = ( i == n ) ? -p : p ) )
{
if ( viz [ i ] ) continue ;
while ( varf >= 2 and determin ( puncte [ st [ varf - 1 ] ] , puncte [ st [ varf ] ] , puncte [ i ] ) < EPS )
viz [ st [ varf -- ] ] = 0 ;
st [ ++ varf ] = i ;
viz [ i ] = 1 ;
}
fout << -- varf << '\n' ;
for ( int i = 1 ; i <= varf ; ++ i )
fout << fixed << setprecision ( 6 ) << puncte [ st [ i ] ].first << ' ' << puncte [ st [ i ] ].second << '\n' ;
return 0;
}