Cod sursa(job #2957975)

Utilizator vladburacBurac Vlad vladburac Data 23 decembrie 2022 23:18:35
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 120 * 1e3;

ifstream fin( "infasuratoare.in" );
ofstream fout( "infasuratoare.out" );

struct Point{
  double x;
  double y;
};
Point v[NMAX];
int n;

int findStartingPoint() {
  int i, ind;
  double miny, minx;
  minx = miny = 1e9 + 1;
  ind = -1;
  for( i = 0; i < n; i++ ) {
    if( v[i].y < miny ) {
      ind = i;
      miny = v[i].y;
      minx = v[i].x;
    }
    else if( v[i].y == miny && v[i].x < minx ) {
      ind = i;
      minx = v[i].x;
    }
  }
  return ind;
}

// orientation > 0 => invers trigonometric
// orientation < 0 => trigonometric
// orientation == 0 => coliniare
inline double orientation( Point a, Point b, Point c ) {
  double compute;
  compute = ( b.y - a.y ) * ( c.x - b.x ) - ( b.x - a.x ) * ( c.y - b.y );
  return compute;
}

inline bool cmp( Point a, Point b ) {
  return orientation( v[0], a, b ) <= 0;
}

vector <Point> convexHull;

void computeHull() {
  int i;
  convexHull.push_back( v[0] );
  convexHull.push_back( v[1] );
  for( i = 2; i < n; i++ ) {
    while( convexHull.size() >= 2 && orientation( convexHull[convexHull.size()-2], convexHull[convexHull.size()-1], v[i] ) >= 0 )
      convexHull.pop_back();
    convexHull.push_back( v[i] );
  }
}
int main() {
  int i, ind;
  fin >> n;
  for( i = 0; i < n; i++ )
    fin >> v[i].x >> v[i].y;
  ind = findStartingPoint();
  swap( v[0], v[ind] );
  sort( v + 1, v + n, cmp );
  computeHull();
  fout << convexHull.size() << "\n";
  for( const Point& p: convexHull )
    fout << p.x << " " << p.y << "\n";
  return 0;
}