Cod sursa(job #2741577)

Utilizator euyoTukanul euyo Data 16 aprilie 2021 15:43:05
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
ifstream fin( "infasuratoare.in" );
ofstream fout( "infasuratoare.out" );
 
const int MaxN = 120001;
 
struct point {
  double x, y;
} p[MaxN];

inline int det( point a, point b, point c ) {
  return (a.x * b.y + b.x * c.y + c.x * a.y - b.x * a.y - a.x * c.y - c.x * b.y);
}

struct cmp_point {
  bool operator () ( const point &a, const point &b ) {
    return (a.x < b.x) || (a.x == b.x && a.y < b.y);	
  }
};
struct cmp_ang {
  bool operator () ( const point &a, const point &b ) {
	return det( p[0], a, b ) > 0; 
  }
};
 
int s[MaxN];
int sp;
 
int main() {
  int n, ind;
  
  fin >> n;
  for ( int i = 0; i < n; ++i ) {
    fin >> p[i].x >> p[i].y;
  }
  sort( p, p + n, cmp_point() );
  sort( p, p + n, cmp_ang() );
  s[sp++] = 0;
  s[sp++] = 1;
  ind = 2;
  while ( ind < n ) {
    while ( sp > 1 && det( p[s[sp - 1]], p[s[sp - 2]], p[ind] ) > 0 ) {
      --sp;       
	}
    s[sp++] = ind++;  
  }
  fout << sp << "\n";
  fout << fixed << setprecision( 6 );
  for ( int i = 0; i < sp; ++i ) {
    fout << p[s[i]].x << " " << p[s[i]].y << "\n"; 	
  }
  fin.close();
  fout.close();
  return 0;
}