Pagini recente » Cod sursa (job #226858) | Cod sursa (job #142870) | Cod sursa (job #626145) | Cod sursa (job #1968804) | Cod sursa (job #2416521)
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std ;
const int NR = 120005 ;
ifstream in ("infasuratoare.in") ;
ofstream out ("infasuratoare.out") ;
pair < double , double > v [ NR ] , st [ NR ] ;
int n ;
double det ( const pair < double , double > & i , const pair < double , double > & j , const pair < double , double > & k ) {
return ( j.x - i.x )*( k.y - i.y ) - ( k.x - i.x )*( j.y - i.y ) ;
}
inline bool cmp ( const pair < double , double > & i , const pair < double , double > & j ) {
return det( v [ 1 ] , i , j ) > 0 ;
}
int main() {
int i , b , k ;
in >> n ;
for ( i = 1 ; i <= n ; ++ i )
in >> v [ i ].x >> v [ i ].y ;
b = 1 ;
for ( i = 2 ; i <= n ; ++ i )
if ( v [ i ] < v [ b ] ) b = i ;
swap ( v [ b ] , v [ 1 ] ) ;
sort ( v + 2 , v + n + 1 , cmp ) ;
st [ 1 ] = v [ 1 ] ;
st [ 2 ] = v [ 2 ] ;
k = 2 ;
for ( i = 3 ; i <= n ; ++ i ) {
while ( k >= 2 && det( st [ k - 1 ] , st [ k ] , v [ i ] ) <= 0 )
k -- ;
st [ ++ k ] = v [ i ] ;
}
out << k << '\n' ;
out << setprecision( 9 ) << fixed ;
for ( i = 1 ; i <= k ; ++ i )
out << st [ i ].x << ' ' << st [ i ].y << '\n' ;
}