Cod sursa(job #2190831)

Utilizator vlad.ulmeanu30Ulmeanu Vlad vlad.ulmeanu30 Data 31 martie 2018 20:09:26
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define maxn 120000

using namespace std;

typedef struct
{
  double px;
  double py;
}poz;

poz v[maxn+5];
int inf[maxn+5];

double ccw ( poz a, poz b, poz c )
{ /// ( x2 - x1 ) * ( y3 - y1 ) - ( y2 - y1 ) * ( x3 - x1 ) < 0 => c este in stanga ab
  double ans1 = ( b.px - a.px ) * ( c.py - a.py ), ans2 = ( b.py - a.py ) * ( c.px - a.px );
  return ans1 - ans2;
}

bool cmp ( poz a, poz b )
{
  return ccw ( v[0], a, b ) < 0;
}

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

  int n;

  fin >> n;

  int i;

  for ( i = 0; i < n; i++ )
    fin >> v[i].px >> v[i].py;

  int np = 0;

  for ( i = 1; i < n; i++ )
    if ( v[0].px > v[i].px || ( v[0].px == v[i].px && v[0].py > v[i].py ) )
      swap ( v[0], v[i] );

  sort ( v + 1, v + n, cmp );

  int nv = 2; /// nr varfuri pe infasuratoare

  inf[0] = 0;
  inf[1] = 1;
  for ( i = 2; i < n; i++ )
  {
    while ( nv >= 2 && ccw ( v[inf[nv-2]], v[inf[nv-1]], v[i] ) >= 0 )
      nv--;

    inf[nv++] = i;
  }

  fout << nv << '\n';

  for ( i = nv - 1; i >= 0; i-- )
    fout << setprecision ( 9 ) << v[inf[i]].px << ' ' << v[inf[i]].py << '\n';

  fin.close ();
  fout.close ();

  return 0;
}