Pagini recente » Cod sursa (job #1147763) | Cod sursa (job #1139301) | Cod sursa (job #1020073) | Cod sursa (job #2650708) | Cod sursa (job #1246842)
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream fin( "infasuratoare.in" );
ofstream fout( "infasuratoare.out" );
const int nmax = 120000;
int n, st[ nmax ];
struct pct{ double x, y; } v[ nmax ];
void read() {
fin >> n;
for( int i = 0; i < n; ++ i ) {
fin >> v[ i ].x >> v[ i ].y;
}
}
bool cmp( pct a, pct b ) {
if ( a.x != b.x ) {
return ( a.x < b.x );
} else {
return ( a.y < b.y );
}
}
bool ccw( pct a, pct b, pct c ) {
double X;
X = ( a.y - b.y ) * c.x + ( b.x - a.x ) * c.y + b.y * a.x - a.y * b.x;
if ( X > 0 ) {
return 0;
}
return 1;
}
int main() {
int ii;
read();
sort( v, v + n, cmp );
ii = 2; st[ 0 ] = 0; st[ 1 ] = 1;
for( int i = 2; i < n; ++ i ) {
while ( ii > 2 && !ccw( v[ st[ ii - 2 ] ], v[ st[ ii - 1 ] ], v[ i ] ) ) {
-- ii;
}
if ( ccw( v[ st[ ii - 2 ] ], v[ st[ ii - 1 ] ], v[ i ] ) ) {
st[ ii ++ ] = i;
} else {
st[ ii - 1 ] = i;
}
}
for( int i = n - 2; i >= 0; -- i ) {
while ( ii > 2 && !ccw( v[ st[ ii - 2 ] ], v[ st[ ii - 1 ] ], v[ i ] ) ) {
-- ii;
}
if ( ccw( v[ st[ ii - 2 ] ], v[ st[ ii - 1 ] ], v[ i ] ) ) {
st[ ii ++ ] = i;
} else {
st[ ii - 1 ] = i;
}
}
fout << ii - 1 << '\n';
fout << setprecision( 6 ) << fixed;
for( int i = 0; i < ii - 1; ++ i ) {
fout << v[ st[ i ] ].x << ' ' << v[ st[ i ] ].y << '\n';
}
fin.close();
fout.close();
return 0;
}