Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Profil Simon2712 | Istoria paginii runda/winter_challenge_1/clasament | Cod sursa (job #412314)
Cod sursa(job #412314)
#include <algorithm>
#include <vector>
using namespace std;
#define INF 0x3f3f3f3f
int N;
vector <int> s;
vector < pair <double, double> > p;
inline double pnt( const pair <double, double> p_1, const pair <double, double> p_2 ) {
if( p_1.first == p_2.first )
return INF;
return ( p_1.second - p_2.second ) / ( p_1.first - p_2.first );
}
inline double sgn( const pair <double, double> p_1, const pair <double, double> p_2, const pair <double, double> p_3 ) {
return ( p_3.second - p_1.second ) * ( p_2.first - p_1.first ) - ( p_3.first - p_1.first ) * ( p_2.second - p_1.second );
}
struct cmp {
bool operator()( const pair <double, double> &p_1, const pair <double, double> &p_2 ) {
return pnt( p[ 0 ], p_1 ) < pnt( p[ 0 ], p_2 );
}
};
int main() {
freopen( "infasuratoare.in", "r", stdin );
freopen( "infasuratoare.out", "w", stdout );
int i;
vector <int> :: iterator it;
scanf( "%d", &N );
p.resize( N );
for( i = 0; i < N; ++i ) {
scanf( "%lf %lf", &p[ i ].first, &p[ i ].second );
if( p[ i ].first < p[ 0 ].first )
swap( p[ i ], p[ 0 ] );
else if( p[ i ].first == p[ 0 ].first && p[ 0 ].second < p[ 0 ].second )
swap( p[ i ], p[ 0 ] );
}
sort( p.begin() + 1, p.end(), cmp() );
s.push_back( 0 );
for( i = 1; i < N; ++i ) {
while( s.size() > 2 && sgn( p[ s[ s.size() - 2 ] ], p[ s[ s.size() - 1 ] ], p[ i ] ) < 0 )
s.pop_back();
s.push_back( i );
}
printf( "%d\n", s.size() );
for( it = s.begin(); it != s.end(); ++it )
printf( "%lf %lf\n", p[ *it ].first,p[ *it ].second );
return 0;
}