Pagini recente » Cod sursa (job #2888761) | Cod sursa (job #1369052) | Cod sursa (job #2154384) | Cod sursa (job #1451748) | Cod sursa (job #2953517)
#include <stdio.h>
#include <vector>
#include <algorithm>
#define NMAXX 120000
using namespace std;
struct Point {
double x, y;
};
vector <Point> convex;
Point v[NMAXX];
int findStartPoint( int n ) {
int start = 0, i;
for ( i = 1; i < n; i++ )
if ( v[i].y < v[start].y || ( v[i].y == v[start].y && v[i].x < v[start].x ) )
start = i;
return start;
}
double orientare( const Point &a, const Point &b, const Point &c ) {
return (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
}
bool cmp( const Point &a, const Point &b ) {
return orientare( v[0], a, b ) < 0;
}
void compute( int n ) {
int i;
convex.push_back( v[0] );
convex.push_back( v[1] );
for ( i = 2; i < n; i++ ) {
while ( convex.size() >= 2 && orientare( convex[convex.size() - 2], convex.back(), v[i] ) >= 0 )
convex.pop_back();
convex.push_back( v[i] );
}
}
int main()
{
FILE *fin, *fout;
int n, i;
fin = fopen( "infasuratoare.in", "r" );
fout = fopen( "infasuratoare.out", "w" );
fscanf ( fin, "%d", &n );
for ( i = 0; i < n; i++ )
fscanf( fin, "%lf%lf", &v[i].x, &v[i].y );
swap( v[0], v[findStartPoint( n )] );
sort( v + 1, v + n, cmp );
compute( n );
fprintf( fout, "%d\n", convex.size() );
for ( const Point &p : convex )
fprintf( fout, "%lf %lf\n", p.x, p.y );
fclose( fin );
fclose( fout );
return 0;
}