Cod sursa(job #3297336)

Utilizator Arhiva_Educationala_2Arhiva Educationala doi Arhiva_Educationala_2 Data 22 mai 2025 14:25:07
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

using ftype = double;
struct Point {
  ftype x, y;
  bool operator < ( const Point& that ) const {
    if( x != that.x )
      return x < that.x;
    return y < that.y;
  }
};

constexpr ftype EPS = 1e-9;
int sgn( ftype x ) { return (x > EPS) - (x < -EPS); }
int sdet( Point A, Point B, Point C ) {
  ftype det = (A.x - B.x) * (A.y - C.y) - (A.y - B.y) * (A.x - C.x);
  return sgn(det);
}

std::vector<Point> hull_half( const std::vector<Point> &v, int sgn ){
  std::vector<Point> ret;
  for( Point P : v ){
    while( (int)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> v ){
  std::sort( v.begin(), v.end() );
  std::vector<Point> ret1 = hull_half( v, +1 );
  std::vector<Point> ret2 = hull_half( v, -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.push_back({ x, y });
  }

  v = hull( v );
  fprintf( fout, "%d\n", (int)v.size() );
  for( auto [x, y]: v )
    fprintf( fout, "%.9lf, %.9lf\n", x, y );

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