Pagini recente » Cod sursa (job #1291460) | Cod sursa (job #2649012) | Cod sursa (job #2514624) | Cod sursa (job #1225639) | Cod sursa (job #2416520)
#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 i.x*j.y + j.x*k.y + k.x*i.y - i.y*j.x - j.y*k.x - k.y*i.x ; // e recomandata forma initiala pt ca sunt mai putine operatii si scade prababilitatea unei erori
}
inline bool cmp ( const pair < double , double > & i , const pair < double , double > & j ) {
return det( v [ 1 ] , i , j ) > 0 ;
}
/*
det > 0 - triunghiul are varful in jos
det > 0 - este convex
sortarea de face astfel descrescator in functie de cate alte puncte sunt " deasupra" dreptei care uneste 1 cu x ;
*/
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 = 1 ; i <= n ; ++ i ) cout << v [ i ].x << ' ' << v [ i ].y << '\n' ;
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' ;
}