Pagini recente » Istoria paginii runda/maricei3/clasament | Cod sursa (job #205149) | Cod sursa (job #783015) | Cod sursa (job #1794351) | Cod sursa (job #1662165)
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
ifstream fin( "infasuratoare.in" ); ofstream fout( "infasuratoare.out" );
const int nmax = 120000;
struct pct{
double x, y;
inline bool operator < ( const pct &a ) const {
if ( x != a.x ) {
return ( x < a.x );
}
return ( y < a.y );
}
} v[ nmax + 1 ];
pct st[ nmax + 1 ];
vector< pct > sol;
inline bool cw( pct a, pct b, pct c ) {
return ( (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x) <= 0 );
}
int main() {
int n;
fin >> n;
for( int i = 1; i <= n; ++ i ) {
fin >> v[ i ].x >> v[ i ].y;
}
sort( v + 1, v + n + 1 );
int t = 0;
st[ ++ t ] = v[ 1 ];
st[ ++ t ] = v[ 2 ];
for( int i = 2; i <= n; ++ i ) {
while ( t >= 2 && cw( st[ t - 1 ], st[ t ], v[ i ] ) ) {
-- t;
}
st[ ++ t ] = v[ i ];
}
for( int i = 1; i <= t; ++ i ) {
sol.push_back( st[ i ] );
}
t = 0;
st[ ++ t ] = v[ n ];
st[ ++ t ] = v[ n - 1 ];
for( int i = n - 2; i > 0; -- i ) {
while ( t >= 2 && cw( st[ t - 1 ], st[ t ], v[ i ] ) ) {
-- t;
}
st[ ++ t ] = v[ i ];
}
for( int i = 2; i < t; ++ i ) {
sol.push_back( st[ i ] );
}
fout << ( int )sol.size() << "\n";
for( int i = 0; i < ( int )sol.size(); ++ i ) {
fout << sol[ i ].x << " " << sol[ i ].y << "\n";
}
fin.close();
fout.close();
return 0;
}