Cod sursa(job #3259830)

Utilizator mircea_007Mircea Rebengiuc mircea_007 Data 27 noiembrie 2024 23:11:15
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

using ll = long long;
using ftype = double;

struct Point {
  ftype x, y;
  Point( ftype x, ftype y ): x(x), y(y) {}
};

int sdet( const Point &a, const Point &b, const Point &c ) {
  ftype det = (a.x - b.x) * (a.y - c.y) - (a.y - b.y) * (a.x - c.x);

  if( det < 0 ) return -1;
  if( det > 0 ) return +1;
  return 0;
}

std::vector<Point> hull_half( const std::vector<Point> &points, int sgn ){
  std::vector<Point> ret;

  for( Point P : points ){
    while( ret.size() >= 2 && sdet( ret.end()[-2], ret.end()[-1], P ) * sgn < 0 )
      ret.pop_back();
    ret.push_back( P );
  }

  return ret;
}

std::vector<Point> hull( std::vector<Point> &points ) {
  std::sort( points.begin(), points.end(), []( const Point &a, const Point &b ) -> bool {
    if( a.x == b.x )
      return a.y < b.y;
    return a.x < b.x;
  } );

  std::vector<Point> ret1 = hull_half( points, +1 );
  std::vector<Point> ret2 = hull_half( points, -1 );

  ret1.insert( ret1.end(), ret2.rbegin() + 1, ret2.rend() - 1 );
  return ret1;
}

int main() {
  FILE *fin = fopen( "infasuratoare.in", "r" );
  FILE *fout = fopen( "infasuratoare.out", "w" );
  
  int n;
  fscanf( fin, "%d", &n );

  std::vector<Point> v;
  for( int i = 0; i < n; i++ ){
    ftype x, y;
    fscanf( fin, "%lf%lf", &x, &y );
    v.emplace_back( x, y );
  }

  v = hull( v );

  fprintf( fout, "%d\n", (int)v.size() );
  for( Point P : v )
    fprintf( fout, "%.6lf %.6lf\n", P.x, P.y );

  fclose( fin );
  fclose( fout );
  return 0;
}