Pagini recente » Cod sursa (job #168120) | Cod sursa (job #2831857) | Cod sursa (job #1572612) | Cod sursa (job #1626188) | Cod sursa (job #2949386)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
const int nmax = 12e4;
struct Point {
float x, y;
};
Point v[nmax];
int st[nmax], k = 0;
float det ( const Point &a, const Point &b, const Point &c ) {
return ( b.x - a.x ) * ( c.y - a.y ) - ( b.y - a.y ) * ( c.x - a.x );
}
bool cmp ( const Point &a, const Point &b ) {
return det ( v[0], a, b ) < 0;
}
ifstream fin ( "infasuratoare.in" );
ofstream fout ( "infasuratoare.out" );
int main() {
int n, ind = 0;
fin >> n >> v[0].x >> v[0].y;
for ( int i = 1; i < n; i++ ) {
fin >> v[i].x >> v[i].y;
if ( v[i].x > v[ind].x || ( v[i].x == v[ind].x && v[i].y > v[ind].y ) )
ind = i;
}
swap ( v[0], v[ind] );
sort ( v + 1, v + n, cmp );
st[k++] = 0;
st[k++] = 1;
for ( int i = 2; i < n; i++ ) {
while ( k > 2 && det ( v[st[k - 2]], v[st[k - 1]], v[i] ) > 0 )
k--;
st[k++] = i;
}
fout << k << '\n';
for ( int i = k - 1; i >= 0; i-- )
fout << fixed << setprecision ( 6 ) << v[st[i]].x << ' ' << v[st[i]].y << '\n';
return 0;
}