Cod sursa(job #2468923)

Utilizator TudorP2006Popescu Tudor TudorP2006 Data 6 octombrie 2019 11:34:35
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include<bits/stdc++.h>

using namespace std;
ifstream fin( "infasuratoare.in" );
ofstream fout( "infasuratoare.out" );
struct puncte {
  double x;
  double y;
} v[100000], stiva[100000];
bool cmp1( puncte a, puncte b ) {
  if ( a.y == b.y )
    return a.x < b.x;
  else
    return a.y < b.y;
}
bool cmp2( puncte a, puncte b ) {
  return atan2( a.y - v[0].y, a.x - v[0].x ) < atan2( b.y - v[0].y, b.x - v[0].x );
}
int main() {
  int n, i, poz;
  fin >> n;
  for ( i = 0; i < n; i++ )
    fin >> v[i].x >> v[i].y;
  sort( v, v + n, cmp1 );
  sort( v + 1, v + n, cmp2 );
  stiva[0] = v[0];
  stiva[1] = v[1];
  poz = 2;
  for ( i = 2; i < n; i++ ) {
    while ( poz >= 2 && (stiva[poz - 1].y - stiva[poz - 2].y) * (v[i].x - stiva[poz - 1].x)  > (v[i].y - stiva[poz - 1].y) * (stiva[poz - 1].x - stiva[poz - 2].x) )
      poz--;
    stiva[poz] = v[i];
    poz++;
  }
  for ( i = 0; i < poz; i++ )
    fout << setprecision(6) << fixed << stiva[i].x << " " << stiva[i].y << "\n";
  return 0;
}