Pagini recente » Cod sursa (job #179425) | Cod sursa (job #215849) | Cod sursa (job #2534832) | Cod sursa (job #2273997) | Cod sursa (job #2743348)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
const int NMAX = 12e4;
const double EPS = 1e-12;
int n;
struct point {
double x, y;
} points[1 + NMAX];
bool point_sort ( point A, point B ) {
if ( A.x == B.x )
return A.y < B.y;
return A.x < B.x;
}
int my_stack[1 + NMAX];
bool visited[1 + NMAX];
double det ( point O, point A, point B ) {
return ( A.x - O.x ) * ( B.y - O.y ) - ( B.x - O.x ) * ( A.y - O.y );
}
int convex_hull () {
sort ( points + 1, points + n + 1, point_sort );
my_stack[1] = 1; my_stack[2] = 2;
int sp = 2; visited[2] = true;
int advance = 1;
for ( int i = 1; i > 0; i += advance ) {
if ( visited[i] == false ) {
while ( sp >= 2 && det ( points[my_stack[sp - 1]], points[my_stack[sp]], points[i] ) < EPS ) {
visited[my_stack[sp]] = false;
sp --;
}
my_stack[++ sp] = i;
visited[i] = true;
}
if ( i == n )
advance = -advance;
}
return sp;
}
ifstream fin ( "infasuratoare.in" );
ofstream fout ( "infasuratoare.out" );
void print_hull ( int sp ) {
fout << sp - 1 << "\n";
fout << setprecision ( 6 ) << fixed;
for ( int i = 1; i < sp; i ++ )
fout << points[my_stack[i]].x << " " << points[my_stack[i]].y << "\n";
}
int main()
{
fin >> n;
for ( int i = 1; i <= n; i ++ ) {
double p, q; fin >> p >> q;
points[i] = { p, q };
}
int stack_pointer = convex_hull ();
print_hull ( stack_pointer );
return 0;
}