Cod sursa(job #2702819)

Utilizator euyoTukanul euyo Data 5 februarie 2021 22:45:16
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 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];

struct angs {
  double val;
  int ind;
} ang[MaxN];

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 angs &a, const angs &b ) {
	return a.val < b.val;
  }
};
 
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 > 0);
}

int order[MaxN];

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() );
  for ( int i = 1; i < n; ++i ) {
    ang[i - 1].val = atan2( p[i].y - p[0].y, p[i].x - p[0].x );
    ang[i - 1].ind = i;
  }
  sort( ang, ang + n - 1, cmp_ang() );
  order[0] = 0;
  for ( int i = 0; i < n - 1; ++i ) {
 	order[i + 1] = ang[i].ind;
  }
  s[sp++] = order[0];
  s[sp++] = order[1];
  ind = 2;
  while ( ind < n ) {
    while ( sp > 1 && det( p[s[sp - 1]], p[s[sp - 2]], p[order[ind]] ) ) {
      --sp;       
	}
    s[sp++] = order[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;
}