Cod sursa(job #2544508)

Utilizator isa_tudor_andreiAndrei Tudor isa_tudor_andrei Data 12 februarie 2020 10:11:09
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 120000;

struct Point{
  long double x, y;
};

Point left_most;
Point v[NMAX + 1], st[NMAX + 1];

bool cmp( Point a, Point b ) {
  return (a.y - left_most.y) * (b.x - left_most.x) > (a.x - left_most.x) * ( b.y - left_most.y );
}

bool isgreater( Point a, Point b, Point add ) {
  return ( b.y - a.y ) * ( add.x - a.x ) < ( add.y - a.y ) * ( b.x - a.x );
}

int main() {
    int n;
    fin>>n;
    left_most = { 1000000001, 1000000001 };
    int ord = 0;
    for( int i = 1; i <= n; i ++ ) {
      fin>>v[i].x>>v[i].y;
      if( v[i].x < left_most.x )
        left_most = v[i], ord = i;
      if( v[i].x == left_most.x )
        left_most.y = v[i].y, ord = i;
    }
    swap( v[1], v[ord] );
    sort( v + 2, v + n + 1, cmp );
    int vf = 0;
    for( int i = 1; i <= n; i ++ ) {
      while( vf > 2 && isgreater( st[vf - 1], st[vf], v[i] ) )
         vf --;
      st[++ vf] = v[i];
    }
    fout<<vf<<"\n";
    for( int i = vf; i >= 1; i -- )
      fout<<fixed<<setprecision(6)<<st[i].x<<" "<<st[i].y<<"\n";
    return 0;
}