Cod sursa(job #2743346)

Utilizator andreic06Andrei Calota andreic06 Data 22 aprilie 2021 20:48:41
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;
const int NMAX = 12e4;
const double ESP = 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;
}

bool visited[1 + NMAX];
int my_stack[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] ) < ESP ) {
            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;
       fout << "\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;
}